//! An implementation of the Knuth-Plass line-breaking algorithm

//! for simple rectangular layouts.

#[cfg(feature = "text_layout_hyphenation")]

use hyphenation::{Hyphenator, Standard};

#[cfg(not(feature = "text_layout_hyphenation"))]

use crate::text3::cache::Standard;

use crate::text3::cache::{

    get_base_direction_from_logical, get_item_measure, is_no_break_space, is_word_separator,

    is_zero_width_space,

    AvailableSpace, BidiDirection, JustifyContent, LayoutError, LoadedFonts,

    LogicalItem, OverflowInfo, ParsedFontTrait, Point, PositionedItem,

    ShapedItem, TextAlign, UnifiedConstraints, UnifiedLayout,

};

const INFINITY_BADNESS: f32 = 10000.0;

const SPACE_STRETCH_RATIO: f32 = 0.5;

const SPACE_SHRINK_RATIO: f32 = 0.33;

const HYPHENATION_PENALTY: f32 = 50.0;

const BADNESS_MULTIPLIER: f32 = 100.0;

/// Represents the elements of a paragraph for the line-breaking algorithm.

#[derive(Debug, Clone)]

enum LayoutNode {

    /// A non-stretchable, non-shrinkable item (a glyph cluster or an object).

    Box(ShapedItem, f32), // Item and its width

    /// A flexible space.

    Glue {

        item: ShapedItem,

        /// Natural width of the space.

        width: f32,

        /// Maximum amount the space can grow beyond its natural width.

        stretch: f32,

        /// Maximum amount the space can shrink below its natural width.

        shrink: f32,

    },

    /// A point where a line break is allowed, with an associated cost.

    Penalty {

        /// Optional item associated with the penalty (e.g., a hyphen glyph).

        item: Option<ShapedItem>,

        width: f32,

        penalty: f32,

    },

}

/// Stores the result of the dynamic programming algorithm for a given point.

#[derive(Debug, Clone, Copy)]

struct Breakpoint {

    /// The total demerit score to reach this point.

    demerit: f32,

    /// The index of the previous breakpoint in the optimal path.

    previous: usize,

    /// The line number this breakpoint ends.

    line: usize,

}

/// Main entry point for the Knuth-Plass layout algorithm.

///

/// This implements optimal line-breaking as described in "Breaking Paragraphs into Lines"

/// (Knuth & Plass, 1981). Unlike greedy algorithms, it considers the entire paragraph

/// to find globally optimal break points.

///

/// # Use Cases

///

/// - `text-wrap: balance` - CSS property for balanced line lengths

/// - High-quality typesetting where line consistency matters

/// - Multi-line headings that should appear visually balanced

///

/// # Limitations

///

/// - Only supports horizontal text (vertical writing modes use greedy algorithm)

/// - Higher computational cost than greedy breaking

/// - May produce different results than browsers for edge cases

/// - overflow-wrap: anywhere/break-word emergency breaks stay greedy-only

///   (word-break / hyphens-driven opportunities ARE honoured here)

// overflow-wrap emergency breaks; the greedy break_one_line path handles this

    // Convert ShapedItems into a sequence of Boxes, Glue, and Penalties.

    // The paragraph base direction gates hyphenation (see 508895 below);

    // the constraints carry word-break/line-break/overflow-wrap so the KP

    // path honours the same soft-wrap controls as the greedy path.

    // Dynamic Programming to find optimal breakpoints

    // Use breakpoints to build and position the final lines

/// Converts a slice of `ShapedItems` into the Box/Glue/Penalty model.

// +spec:line-breaking:16e64c - soft wrap opportunity controls (word-break, overflow-wrap, line-break) threaded via UnifiedConstraints

#[allow(clippy::too_many_lines)] // large but cohesive: single-purpose layout/render/parse routine (one branch per case)

        // +spec:line-breaking:f12241 - shaping across intra-word breaks: shaped clusters preserve joining forms

                // NBSP & friends (UAX#14 class GL/WJ) add word-spacing Glue but are NOT

                // soft-wrap opportunities, so suppress the break Penalty for them —

                // otherwise "1\u{00A0}km" could wrap between the number and unit.

            }

                // 1. Collect all adjacent clusters to form a full "word".

                        // Stop collecting *before* any soft-wrap boundary so the outer

                        // loop can emit the correct node for it. Word separators are

                        // shaped as ordinary Clusters (text " "), so without these guards

                        // the greedy collection would absorb every space into one giant

                        // "word" and the paragraph could never break — it would collapse

                        // onto a single line. Boundaries handled by the outer loop:

                        //   * word separator     -> Glue + Penalty (soft wrap)

                        //   * zero-width space    -> Penalty (soft wrap)

                        //   * cluster ending '-'  -> Box + zero-width Penalty

                        //     (+spec:line-breaking:2d3674 — U+002D/U+2010 are UAX#14

                        //     class BA break opportunities AFTER the hyphen; a hyphen

                        //     occurs mid-word, e.g. "well-being").

                        {

                    } else {

                        // Stop if we hit a non-cluster item (object, tab, break, etc.)

                    }

                }

                // +spec:line-breaking:28a40b - Hyphenation is a rendering-only effect (no change to underlying content)

                // +spec:line-breaking:f23fe8 - UA may use language-tailored heuristics (delegated to hyphenation crate)

                // 2. Try to find all hyphenation opportunities for this word.

                // +spec:display-property:508895 - hyphenation of direction-mismatched words is suppressed

                // (CSS 2.2 §9.10 note: hyphenating an LTR word inside an RTL

                // paragraph - or vice versa - would render the hyphen visually

                // MID-line rather than at the line edge, so UAs usually

                // suppress it. The word's direction comes from its first

                // cluster; the paragraph's from the logical items.)

                    )

                    // No hyphenation possible, add the whole word as boxes -

                    // with the SAME soft-wrap opportunities between clusters

                    // the greedy path grants (word-break: break-all breaks

                    // between any two clusters, `normal` between CJK ones,

                    // keep-all suppresses those; the shared predicate is the

                    // single source of truth). Without this, `text-wrap:

                    // balance` (the KP path) silently ignored word-break and

                    // CJK runs never gained intra-word breaks.

                            )

                    }

                } else {

                    // 3. Convert word + hyphenation breaks into a sequence of Boxes and Penalties.

                        // Add the items that form the next syllable (the part between the last

                        // break and this one)

                    }

                    // Add the final remainder of the word.

                    } else {

                        // This case happens if find_all_hyphenation_breaks returned an empty vec.

                        // Fallback to just adding the original word.

                    }

                }

            }

            // Per CSS Text 3 §5.1: "there is a soft wrap opportunity before and

            // after each replaced element or other atomic inline"

        }

    }

    // Anchor the end of the paragraph. Standard Knuth-Plass appends a finishing

    // forced break so the final line is broken at the paragraph end. Without it,

    // a paragraph that ends in an ordinary word (its final nodes are Box, not a

    // Penalty) never sets breakpoints[n] in the DP, so the backtrack collapses

    // the entire paragraph onto a single line. A forced break at the end makes

    // n a legal breakpoint regardless of the last node's type; the forced-break

    // scoring in find_optimal_breakpoints already exempts a short last line from

    // any badness, so no finishing glue is required. The penalty carries no item,

    // so it contributes nothing to the positioned output.

        )

/// Uses dynamic programming to find the optimal set of line breaks.

#[allow(clippy::match_same_arms)] // enum/value mapping/dispatch table: one arm per input variant (or cross-type bindings that can't merge)

#[allow(clippy::too_many_lines)] // large but cohesive: single-purpose layout/render/parse routine (one branch per case)

#[allow(clippy::cognitive_complexity)] // cohesive Knuth-Plass DP: one branch per break class

    // For MinContent (intrinsic min-content sizing), CSS wants the width of the

    // widest unbreakable unit (word). Break at EVERY legal opportunity so each

    // word lands on its own line; the widest resulting line then equals the

    // widest word. The optimizing DP below cannot express this: with an

    // effectively infinite width it puts the whole paragraph on one line, making

    // min-content == max-content. Every Penalty node is a legal break point.

        }

        // Ensure the final segment (which may end in Box nodes) forms a line.

    // For Knuth-Plass, we need a definite line width.

    //

    // For MaxContent, use a very large value (no line breaks unless forced).

    // The actual min-content width is determined by the widest resulting line.

        // MinContent is handled by the early return above; keep a large width as

        // a defensive fallback so this arm never breaks after every character.

    };

    // (and lines after forced breaks when each-line is set). The hanging keyword would

    // invert this, indenting all lines EXCEPT the first.

    } else {

    };

    } else {

    };

    // Prefix sums for O(1) range queries (eliminates O(n³) inner loop).

    //

    // Knuth-Plass counts a Penalty's width ONLY when the line breaks AT that

    // penalty (the hyphen is rendered at the split, nowhere else - CSS Text 3

    // §5.3). Interior hyphenation opportunities therefore contribute ZERO to

    // a candidate line's width: keep penalties out of `prefix_width` and add

    // the break-node's own width explicitly in the DP loop. The old sums

    // inflated every candidate by one hyphen width per unused opportunity,

    // and the positioner then rendered a "-" at every opportunity mid-line.

            LayoutNode::Glue {

                ..

        };

    }

    ];

        // Optimization:

        //

        // A legal line break can only occur at a Penalty node. If the current node

        // is a Box or Glue, we can skip it as a potential breakpoint.

        // Width the hyphen (or other penalty item) adds IF the line breaks here.

        };

            // Calculate the properties of a potential line from node `j` to `i`.

            // O(1) range sum via prefix sums: sum of nodes[j..=i], plus the

            // width of the penalty broken at (see the prefix-sum note above).

            } else {

            };

            // Calculate adjustment ratio. If the line is wider than the available width

            // but has no glue to shrink, it is an invalid candidate.

                } else {

                }

                } else {

                    // Overfull with nothing to shrink: this line physically cannot

                    // fit, so it is INFEASIBLE — not merely "loose". Marking it with a

                    // large negative ratio makes the `ratio < -1.0` guard below reject

                    // it, exactly like an over-shrunk line. Using +INFINITY_BADNESS

                    // here (a positive ratio) was a bug: it let an overflowing line

                    // survive the feasibility guard and then be rewarded by the forced

                    // end-of-paragraph break, so the DP preferred one overflowing line

                    // over a legal break (e.g. after a mid-word hyphen). Overlong

                    // unbreakable content is intentionally left to the greedy path.

                }

            } else {

            };

            // Lines that must shrink too much (or that overflow with no shrink) are

            // invalid and cannot start an optimal path.

            // Calculate badness

            // Add penalty for the break point

            // TODO: Add demerits for consecutive lines with very different

            // ratios (fitness classes).

            //

            // For now, demerit is simply the cumulative badness.

        }

    }

    // Backtrack from the end to find the break points

/// Takes the optimal break points and performs the final positioning.

#[allow(clippy::suboptimal_flops)] // mul_add not guaranteed faster/available without target +fma; keep explicit a*b+c

#[allow(clippy::cast_precision_loss)] // bounded graphics/coord/counter/fixed-point cast

#[allow(clippy::match_same_arms)] // enum/value mapping/dispatch table: one arm per input variant (or cross-type bindings that can't merge)

#[allow(clippy::too_many_lines)] // large but cohesive: single-purpose layout/render/parse routine (one branch per case)

        // A Penalty's item (the synthesized hyphen) renders ONLY when the

        // line actually breaks at that penalty - i.e. for the LAST node of

        // the span. Cloning every penalty's item drew a "-" at each interior

        // hyphenation opportunity (CSS Text 3 §5.3: hyphenation visually

        // indicates the split, at the split).

        // +spec CSS Text 3 §4.1.2: a line's trailing (line-terminating) spaces

        // "hang" — they are removed before measuring the line and are not counted

        // as justification opportunities. The break index sits just past the

        // Penalty following the trailing Glue, so that space is the last item

        // here. Drop trailing word separators so line_width, the justification

        // space count, and positioning all exclude them (matching the greedy

        // break_one_line path, which trims trailing spaces).

        // Note: Calculate spacing, do not mutate items

        // the last line and lines ending with a forced break

        ));

        );

        // +spec:display-contents:858337 - text-align justification: last line start-aligned, justify-all forces last line justify

        // +spec:display-property:50e074 - justify stretches spaces/words in inline boxes, not inline-table/inline-block

        // +spec:display-property:ce8d54 - text-justify selects justification method, inherited from block containers to root inline box

        // Justify ONLY when the RESOLVED alignment says so.

        // `resolve_effective_alignment` already encodes the last-line and

        // forced-break rules (§6.1/§6.3: Justify degrades to Start there,

        // JustifyAll does not), so no extra last-line disjunct belongs here.

        // The old gate justified every non-last line whenever text-justify

        // was not `none` - which is its DEFAULT (`auto` -> InterWord) - so

        // `text-align: left/center/right` paragraphs came out justified, and

        // lines before a forced break were justified against §6.3. The

        // greedy path documents the same trap (see cache.rs

        // "Without this check, ALL text gets justified").

                TextAlign::Justify | TextAlign::JustifyAll

            );

        // Get the available width as f32 for calculations

        // For MinContent/MaxContent, we use the actual computed line_width

        // since there's no "available" space to justify into.

        };

        // Alignment & Positioning

        // For MaxContent, don't apply alignment (treat as left-aligned)

            AvailableSpace::MaxContent | AvailableSpace::MinContent

        );

        } else {

        };

        // +spec:writing-modes:155a06 - resolve start/end edges of line box per bidi direction

        };

        // +spec:display-contents:5a1b30 - overflowing lines are start-aligned (overflow off end edge)

        } else {

            }

        };

        // +spec:display-contents:21b27a - text-indent applies to initial letter's originating line as usual

        // +spec:line-breaking:bc389d - text-indent with each-line/hanging keywords

            // TODO: with text-indent-each-line, also detect lines after forced breaks in the KP path

            } else {

            };

                }

            };

            // Apply extra spacing to the pen

        }

        // +spec:box-model:96f5a7 - line box height uses line-height only; inline margins/borders/padding do not enter calculation

    }

    // Record the unclipped content bounds. `overflow_items` stays empty by

    // design: every item is positioned (visual overflow is clipped at paint

    // time), so nothing is dropped here. TODO(superplan): populate

    // `overflow_items` only if a path actually discards content that doesn't fit.

#[cfg(test)]

mod kp_fix_tests {

    use super::*;

    use crate::text3::cache::{ShapedCluster, StyleProperties, UnifiedConstraints};

    use azul_core::selection::{ContentIndex, GraphemeClusterId};

    use azul_css::props::basic::FontRef;

    use std::sync::Arc;

        // Build per-grapheme clusters like the real shaper. 12px letters, 6px '-', 5px space.

                };

        )

    #[test]

        // "aaaa aaaa" (ends in a Box, no trailing space) must wrap at width 60.

    #[test]

        // "aaaa-aaaa": a zero-width penalty must follow the '-' Box.

        // find the '-' box and assert the next node is a zero-width penalty

                        }

                    }

        }

        // and it must actually enable a wrap at width 60

    #[test]

        // "aaaa aaaa" min-content: two words => two content lines (widest = one word).

        // there must be a break after the first word's trailing space penalty,

        // i.e. more than one break -> not a single spanning line.

    #[test]

        // "aaaa aaaa" @60 wraps to [.., 6, 11]; line 0 = "aaaa" + trailing space.

        // The line-terminating space must not be positioned on line 0.

        // Rightmost cluster edge on line 0 == 4*12 = 48px (not 53 incl. the space).

}

#[cfg(test)]

#[allow(clippy::float_cmp)] // exact geometry: every advance below is an exact f32

#[allow(clippy::cast_precision_loss)] // small line counters

mod autotest_generated {

    use std::sync::Arc;

    use azul_core::selection::{ContentIndex, GraphemeClusterId};

    use azul_css::props::basic::FontRef;

    use super::*;

    use crate::text3::cache::{

        BreakType, ClearType, InlineBreak, InlineContent, LineHeight, Rect, ShapedCluster,

        StyleProperties,

    };

    // ---------------------------------------------------------------------

    // Builders. Every item is a single-grapheme cluster with an explicit

    // advance, mirroring what the shaper produces: 12px letters, 5px space,

    // 6px hyphen. No glyphs -> get_item_measure() == advance exactly, so all

    // expected coordinates below are exact integers.

    // ---------------------------------------------------------------------

    fn cl(text: &str, advance: f32) -> ShapedItem {

        ShapedItem::Cluster(ShapedCluster {

            flags: crate::text3::cache::ClusterFlags::classify(text),

            source_text: Arc::from(text), source_byte_len: text.len() as u16,

            source_cluster_id: GraphemeClusterId {

                source_run: 0,

                start_byte_in_run: 0,

            },

            source_content_index: ContentIndex {

                run_index: 0,

                item_index: 0,

            },

            source_node_id: None,

            glyphs: smallvec::SmallVec::new(),

            advance,

            direction: BidiDirection::Ltr,

            style: Arc::new(StyleProperties::default()),

            marker_position_outside: None,

            is_first_fragment: true,

            is_last_fragment: true,

        })

    }

    fn advance_of(c: char) -> f32 {

        match c {

            ' ' => 5.0,

            '-' => 6.0,

            _ => 12.0,

        }

    }

    /// One cluster per `char`, like the real shaper hands to `kp_layout`.

    fn items_of(text: &str) -> Vec<ShapedItem> {

        text.chars()

            .map(|c| cl(&c.to_string(), advance_of(c)))

            .collect()

    }

    fn no_fonts() -> LoadedFonts<FontRef> {

        LoadedFonts::new()

    }

    /// `convert_items_to_nodes` with hyphenation disabled (the hyphenator is a

    /// feature-gated type and needs a real dictionary; `None` is the path the

    /// engine takes whenever `hyphens: none`).

    fn nodes_of(items: &[ShapedItem]) -> Vec<LayoutNode> {

        convert_items_to_nodes(

            items,

            None,

            &no_fonts(),

            &UnifiedConstraints::default(),

            BidiDirection::Ltr,

        )

    }

    fn nodes_for(text: &str) -> Vec<LayoutNode> {

        nodes_of(&items_of(text))

    }

    fn definite(width: f32) -> UnifiedConstraints {

        UnifiedConstraints {

            available_width: AvailableSpace::Definite(width),

            ..Default::default()

        }

    }

    fn object(width: f32) -> ShapedItem {

        ShapedItem::Object {

            source: ContentIndex {

                run_index: 0,

                item_index: 0,

            },

            bounds: Rect {

                x: 0.0,

                y: 0.0,

                width,

                height: 10.0,

            },

            baseline_offset: 0.0,

            content: InlineContent::Tab {

                style: Arc::new(StyleProperties::default()),

            },

        }

    }

    fn tab(width: f32) -> ShapedItem {

        ShapedItem::Tab {

            source: ContentIndex {

                run_index: 0,

                item_index: 0,

            },

            bounds: Rect {

                x: 0.0,

                y: 0.0,

                width,

                height: 10.0,

            },

        }

    }

    fn hard_break() -> ShapedItem {

        ShapedItem::Break {

            source: ContentIndex {

                run_index: 0,

                item_index: 0,

            },

            break_info: InlineBreak {

                break_type: BreakType::Hard,

                clear: ClearType::None,

                content_index: 0,

            },

        }

    }

    fn rtl_logical() -> Vec<LogicalItem> {

        vec![LogicalItem::Text {

            source: ContentIndex {

                run_index: 0,

                item_index: 0,

            },

            text: Arc::from("\u{05E9}\u{05DC}\u{05D5}\u{05DD}"), // "שלום"

            style: Arc::new(StyleProperties::default()),

            marker_position_outside: None,

            source_node_id: None,

        }]

    }

    // ---------------------------------------------------------------------

    // Inspectors

    // ---------------------------------------------------------------------

    fn is_forced(node: &LayoutNode) -> bool {

        matches!(node, LayoutNode::Penalty { penalty, .. } if *penalty <= -INFINITY_BADNESS)

    }

    fn penalty_count(nodes: &[LayoutNode]) -> usize {

        nodes

            .iter()

            .filter(|n| matches!(n, LayoutNode::Penalty { .. }))

            .count()

    }

    fn line_text(layout: &UnifiedLayout, line: usize) -> String {

        layout

            .items

            .iter()

            .filter(|it| it.line_index == line)

            .filter_map(|it| it.item.as_cluster().map(|c| c.text()))

            .collect()

    }

    fn line_count(layout: &UnifiedLayout) -> usize {

        layout

            .items

            .iter()

            .map(|it| it.line_index + 1)

            .max()

            .unwrap_or(0)

    }

    fn line_left(layout: &UnifiedLayout, line: usize) -> f32 {

        layout

            .items

            .iter()

            .filter(|it| it.line_index == line)

            .map(|it| it.position.x)

            .fold(f32::INFINITY, f32::min)

    }

    fn line_right(layout: &UnifiedLayout, line: usize) -> f32 {

        layout

            .items

            .iter()

            .filter(|it| it.line_index == line)

            .map(|it| it.position.x + get_item_measure(&it.item, false))

            .fold(f32::NEG_INFINITY, f32::max)

    }

    /// Structural contract of `find_optimal_breakpoints`: the returned indices

    /// are strictly increasing, in range, and the paragraph ends at `n`.

    fn assert_breaks_well_formed(nodes: &[LayoutNode], breaks: &[usize], what: &str) {

        for w in breaks.windows(2) {

            assert!(

                w[0] < w[1],

                "{what}: breaks must be strictly increasing, got {breaks:?}"

            );

        }

        for &b in breaks {

            assert!(

                b <= nodes.len(),

                "{what}: break {b} out of range (n = {})",

                nodes.len()

            );

        }

        if !breaks.is_empty() {

            assert_eq!(

                *breaks.last().unwrap(),

                nodes.len(),

                "{what}: the paragraph must end at the last node"

            );

        }

    }

    // =====================================================================

    // convert_items_to_nodes: structure of the Box/Glue/Penalty stream

    // =====================================================================

    #[test]

    fn convert_empty_items_yields_no_nodes() {

        // The terminal-forced-break append is guarded on !nodes.is_empty(),

        // so an empty paragraph must stay empty (not gain a lone penalty).

        assert!(nodes_of(&[]).is_empty());

    }

    #[test]

    fn convert_appends_exactly_one_terminal_forced_break() {

        let nodes = nodes_for("ab cd");

        assert!(is_forced(nodes.last().unwrap()), "paragraph must be anchored");

        assert_eq!(

            nodes.iter().filter(|n| is_forced(n)).count(),

            1,

            "exactly one forced break for a paragraph with no explicit breaks"

        );

    }

    #[test]

    fn convert_does_not_duplicate_terminal_break_after_an_explicit_break() {

        let items = vec![cl("a", 12.0), hard_break()];

        let nodes = nodes_of(&items);

        assert_eq!(nodes.len(), 2, "Box + the Break's own forced Penalty, no more");

        assert!(is_forced(&nodes[1]));

        assert_eq!(nodes.iter().filter(|n| is_forced(n)).count(), 1);

    }

    #[test]

    fn convert_space_glue_uses_the_documented_stretch_shrink_ratios() {

        let nodes = nodes_for("a b");

        let glue = nodes

            .iter()

            .find(|n| matches!(n, LayoutNode::Glue { .. }))

            .expect("a space must become Glue");

        match glue {

            LayoutNode::Glue {

                width,

                stretch,

                shrink,

                ..

            } => {

                assert_eq!(*width, 5.0);

                assert_eq!(*stretch, 5.0 * SPACE_STRETCH_RATIO);

                assert_eq!(*shrink, 5.0 * SPACE_SHRINK_RATIO);

                assert!(

                    *shrink < *width,

                    "a space may never shrink past zero width"

                );

            }

            _ => unreachable!(),

        }

    }

    #[test]

    fn convert_zero_width_space_becomes_an_itemless_penalty() {

        // U+200B is a wrap opportunity with no glyph: it must produce a

        // zero-width, zero-cost Penalty and contribute no Box.

        let items = vec![cl("a", 12.0), cl("\u{200B}", 0.0), cl("b", 12.0)];

        let nodes = nodes_of(&items);

        let zwsp = match &nodes[1] {

            LayoutNode::Penalty {

                item,

                width,

                penalty,

            } => (item.is_none(), *width, *penalty),

            other => panic!("expected a Penalty for U+200B, got {other:?}"),

        };

        assert_eq!(zwsp, (true, 0.0, 0.0));

        // ...and it really is a break opportunity at a narrow width.

        let breaks = find_optimal_breakpoints(&nodes, &definite(12.0));

        assert_breaks_well_formed(&nodes, &breaks, "zwsp");

    }

    #[test]

    fn convert_both_hyphen_codepoints_are_soft_wrap_opportunities() {

        // U+002D HYPHEN-MINUS and U+2010 HYPHEN are UAX#14 class BA: a break is

        // allowed AFTER them, and no extra hyphen glyph is inserted.

        for hyphen in ['\u{002D}', '\u{2010}'] {

            let items = vec![cl("a", 12.0), cl(&hyphen.to_string(), 6.0), cl("b", 12.0)];

            let nodes = nodes_of(&items);

            match (&nodes[1], &nodes[2]) {

                (

                    LayoutNode::Box(ShapedItem::Cluster(c), w),

                    LayoutNode::Penalty {

                        item,

                        width,

                        penalty,

                    },

                ) => {

                    assert_eq!(c.text(), hyphen.to_string());

                    assert_eq!(*w, 6.0);

                    assert!(item.is_none(), "no extra hyphen glyph may be inserted");

                    assert_eq!(*width, 0.0);

                    assert!(

                        *penalty > -INFINITY_BADNESS,

                        "the hyphen break is optional, not forced"

                    );

                }

                other => panic!("expected Box('{hyphen}') + zero-width Penalty, got {other:?}"),

            }

        }

    }

    #[test]

    fn convert_atomic_inline_is_wrapped_in_wrap_opportunities() {

        // CSS Text 3 §5.1: a soft wrap opportunity exists before AND after each

        // replaced element / atomic inline.

        let nodes = nodes_of(&[object(40.0)]);

        assert!(matches!(nodes[0], LayoutNode::Penalty { .. }));

        assert!(matches!(nodes[1], LayoutNode::Box(_, w) if w == 40.0));

        assert!(matches!(nodes[2], LayoutNode::Penalty { .. }));

    }

    #[test]

    fn convert_tab_is_glue_and_not_a_wrap_opportunity() {

        // A tab is stretchable like a space but is NOT followed by a Penalty,

        // so no line may break at it.

        let nodes = nodes_of(&[cl("a", 12.0), tab(30.0), cl("b", 12.0)]);

        match &nodes[1] {

            LayoutNode::Glue {

                width,

                stretch,

                shrink,

                ..

            } => {

                assert_eq!(*width, 30.0);

                assert_eq!(*stretch, 30.0 * SPACE_STRETCH_RATIO);

                assert_eq!(*shrink, 30.0 * SPACE_SHRINK_RATIO);

            }

            other => panic!("a tab must become Glue, got {other:?}"),

        }

        assert_eq!(

            penalty_count(&nodes),

            1,

            "only the terminal forced break; a tab offers no wrap opportunity"

        );

    }

    #[test]

    fn nbsp_must_not_be_a_soft_wrap_opportunity() {

        // UAX#14 class GL. cache.rs suppresses NBSP /

        // NNBSP / WJ / ZWNBSP as break opportunities in the greedy path

        // (`is_break_opportunity_with_word_break`, "otherwise 10\u{00A0}km

        // wrongly wraps"), but convert_items_to_nodes keys off

        // `is_word_separator`, which reports NBSP as a separator -- so the

        // Knuth-Plass path emits Glue + Penalty and "10\u{00A0}km" CAN wrap at

        // the no-break space. See the report accompanying this test batch.

        for nbsp in ['\u{00A0}', '\u{202F}'] {

            let items = vec![cl("1", 12.0), cl(&nbsp.to_string(), 5.0), cl("k", 12.0)];

            let nodes = nodes_of(&items);

            let optional_breaks = nodes

                .iter()

                .filter(|n| matches!(n, LayoutNode::Penalty { .. }) && !is_forced(n))

                .count();

            assert_eq!(

                optional_breaks, 0,

                "U+{:04X} is a no-break space: it must not offer a wrap opportunity, got {nodes:?}",

                nbsp as u32

            );

        }

    }

    #[test]

    fn cjk_run_gains_inter_character_wrap_opportunities() {

        // U+3000 stays a non-separator (CSS Text §7.1), but word-break is

        // threaded through kp_layout now: under `normal`, CJK clusters offer

        // a soft-wrap opportunity after each ideograph, exactly like the

        // greedy path (line-breaking:16e64c). Two inter-cluster penalties +

        // the terminal forced break.

        let items = vec![cl("\u{4E00}", 16.0), cl("\u{3000}", 16.0), cl("\u{4E8C}", 16.0)];

        let nodes = nodes_of(&items);

        assert_eq!(

            penalty_count(&nodes),

            3,

            "two CJK inter-character opportunities plus the terminal break"

        );

        let breaks = find_optimal_breakpoints(&nodes, &definite(20.0));

        assert_breaks_well_formed(&nodes, &breaks, "cjk");

        // And the run actually wraps at 20px now.

        assert!(breaks.len() >= 2, "the CJK run must wrap: {breaks:?}");

    }

    #[test]

    fn convert_survives_hostile_unicode_without_panicking() {

        // Combining marks, an emoji ZWJ sequence, RTL text, a lone surrogate is

        // impossible in Rust, so use the next-worst thing: unpaired combining

        // marks, an unassigned plane-15 codepoint, and a zero-advance cluster.

        let items = vec![

            cl("e\u{0301}", 12.0),

            cl("\u{1F468}\u{200D}\u{1F469}\u{200D}\u{1F467}", 48.0),

            cl("\u{05D0}", 12.0),

            cl("\u{FFFD}", 12.0),

            cl("\u{F0000}", 0.0),

            cl("", 0.0),

        ];

        let nodes = nodes_of(&items);

        // Nothing is a separator or a hyphen, so every cluster stays a Box.

        assert_eq!(

            nodes.iter().filter(|n| matches!(n, LayoutNode::Box(..))).count(),

            items.len()

        );

        let layout = kp_layout(&items, &[], &definite(30.0), None, &no_fonts());

        assert_eq!(

            layout.items.len(),

            items.len(),

            "no cluster may be dropped by the layout"

        );

    }

    // =====================================================================

    // find_optimal_breakpoints: numeric limits & structural invariants