Grcov report - knuth

1

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

2

//! for simple rectangular layouts.

3

4

#[cfg(feature = "text_layout_hyphenation")]

5

use hyphenation::{Hyphenator, Standard};

6

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

7

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

8

9

use crate::text3::cache::{

10

    get_base_direction_from_logical, get_item_measure, is_word_separator, is_zero_width_space,

11

    AvailableSpace, BidiDirection, JustifyContent, LayoutError, LoadedFonts,

12

    LogicalItem, OverflowInfo, ParsedFontTrait, Point, PositionedItem,

13

    ShapedItem, TextAlign, UnifiedConstraints, UnifiedLayout,

14

};

15

16

const INFINITY_BADNESS: f32 = 10000.0;

17

18

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

19

#[derive(Debug, Clone)]

20

enum LayoutNode {

21

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

22

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

23

    /// A flexible space.

24

    Glue {

25

        item: ShapedItem,

26

        /// Natural width of the space.

27

        width: f32,

28

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

29

        stretch: f32,

30

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

31

        shrink: f32,

32

},

33

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

34

    Penalty {

35

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

36

        item: Option<ShapedItem>,

37

        width: f32,

38

        penalty: f32,

39

},

40

41

42

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

43

#[derive(Debug, Clone, Copy)]

44

struct Breakpoint {

45

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

46

    demerit: f32,

47

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

48

    previous: usize,

49

    /// The line number this breakpoint ends.

50

    line: usize,

51

52

53

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

54

///

55

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

56

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

57

/// to find globally optimal break points.

58

///

59

/// # Use Cases

60

///

61

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

62

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

63

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

64

///

65

/// # Limitations

66

///

67

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

68

/// - Higher computational cost than greedy breaking

69

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

70

/// - Does not yet handle overflow-wrap: anywhere/break-word (handled in greedy path)

71

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

72

pub(crate) fn kp_layout<T: ParsedFontTrait>(

73

    items: &[ShapedItem],

74

    logical_items: &[LogicalItem],

75

    constraints: &UnifiedConstraints,

76

    hyphenator: Option<&Standard>,

77

    fonts: &LoadedFonts<T>,

78

) -> Result<UnifiedLayout, LayoutError> {

79

    if items.is_empty() {

80

        return Ok(UnifiedLayout {

81

            items: Vec::new(),

82

            overflow: OverflowInfo::default(),

83

});

84

85

86

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

87

    let nodes = convert_items_to_nodes(items, hyphenator, fonts);

88

89

    // Dynamic Programming to find optimal breakpoints

90

    let breaks = find_optimal_breakpoints(&nodes, constraints);

91

92

    // Use breakpoints to build and position the final lines

93

    let final_layout: UnifiedLayout =

94

        position_lines_from_breaks(&nodes, &breaks, logical_items, constraints);

95

96

    Ok(final_layout)

97

98

99

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

100

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

101

fn convert_items_to_nodes<T: ParsedFontTrait>(

102

    items: &[ShapedItem],

103

    hyphenator: Option<&Standard>,

104

    fonts: &LoadedFonts<T>,

105

) -> Vec<LayoutNode> {

106

    let mut nodes = Vec::new();

107

    let is_vertical = false; // Knuth-Plass is horizontal-only for now

108

    let mut item_iter = items.iter().peekable();

109

110

    while let Some(item) = item_iter.next() {

111

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

112

        // NOTE: word-break property is not yet threaded through to kp_layout.

113

        // Currently uses normal break behavior (spaces are break opportunities).

114

        // To fully support break-all/keep-all, UnifiedConstraints.word_break

115

        // would need to be passed here and used to insert additional Penalty

116

        // nodes between CJK clusters (normal) or between all clusters (break-all),

117

        // or suppress CJK inter-character penalties (keep-all).

118

        match item {

119

            item if is_zero_width_space(item) => {

120

                nodes.push(LayoutNode::Penalty {

121

                    item: None,

122

                    width: 0.0,

123

                    penalty: 0.0,

124

});

125

126

            item if is_word_separator(item) => {

127

                let width = get_item_measure(item, is_vertical);

128

                nodes.push(LayoutNode::Glue {

129

                    item: item.clone(),

130

                    width,

131

                    stretch: width * 0.5,

132

                    shrink: width * 0.33,

133

});

134

                nodes.push(LayoutNode::Penalty {

135

                    item: None,

136

                    width: 0.0,

137

                    penalty: 0.0,

138

});

139

140

            ShapedItem::Cluster(cluster)

141

                if cluster.text.ends_with('\u{002D}')

142

                    || cluster.text.ends_with('\u{2010}') =>

143

144

                let width = get_item_measure(item, is_vertical);

145

                nodes.push(LayoutNode::Box(item.clone(), width));

146

                // +spec:line-breaking:2d3674 - U+002D/U+2010 are soft wrap opportunities, not hyphenation opportunities (no extra glyph inserted)

147

                // Zero-width penalty: allows a line break after the visible

148

                // hyphen character without inserting an additional hyphen glyph.

149

                nodes.push(LayoutNode::Penalty {

150

                    item: None,

151

                    width: 0.0,

152

                    penalty: 0.0,

153

});

154

155

            ShapedItem::Cluster(cluster) => {

156

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

157

                let mut current_word_clusters = vec![cluster.clone()];

158

                while let Some(peeked_item) = item_iter.peek() {

159

                    if let ShapedItem::Cluster(next_cluster) = peeked_item {

160

                        current_word_clusters.push(next_cluster.clone());

161

                        item_iter.next(); // Consume the peeked item

162

                    } else {

163

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

164

                        break;

165

166

167

168

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

169

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

170

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

171

                // +spec:display-property:508895 - cross-direction hyphenation suppression (LTR in RTL / RTL in LTR) not yet implemented

172

                let hyphenation_breaks = hyphenator.and_then(|h| {

173

                    crate::text3::cache::find_all_hyphenation_breaks(

174

                        &current_word_clusters,

175

h,

176

                        is_vertical,

177

                        fonts,

178

179

});

180

181

                if hyphenation_breaks.is_none() {

182

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

183

                    for c in current_word_clusters {

184

                        nodes.push(LayoutNode::Box(ShapedItem::Cluster(c.clone()), c.advance));

185

186

                } else {

187

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

188

                    let breaks = hyphenation_breaks.unwrap();

189

                    let mut current_item_cursor = 0;

190

191

                    for b in breaks.iter() {

192

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

193

                        // break and this one)

194

                        let num_items_in_syllable = b.line_part.len() - current_item_cursor;

195

                        for item in b.line_part.iter().skip(current_item_cursor) {

196

                            nodes.push(LayoutNode::Box(

197

                                item.clone(),

198

                                get_item_measure(item, is_vertical),

199

));

200

201

                        current_item_cursor += num_items_in_syllable;

202

203

                        let hyphen_measure = get_item_measure(&b.hyphen_item, is_vertical);

204

                        nodes.push(LayoutNode::Penalty {

205

                            item: Some(b.hyphen_item.clone()),

206

                            width: hyphen_measure,

207

                            penalty: 50.0, // Standard penalty for hyphenation

208

});

209

210

211

                    // Add the final remainder of the word.

212

                    if let Some(last_break) = breaks.last() {

213

                        for remainder_item in &last_break.remainder_part {

214

                            nodes.push(LayoutNode::Box(

215

                                remainder_item.clone(),

216

                                get_item_measure(remainder_item, is_vertical),

217

));

218

219

                    } else {

220

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

221

                        // Fallback to just adding the original word.

222

                        for c in current_word_clusters {

223

                            nodes.push(LayoutNode::Box(ShapedItem::Cluster(c.clone()), c.advance));

224

225

226

227

228

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

229

            // after each replaced element or other atomic inline"

230

            ShapedItem::Object { .. } | ShapedItem::CombinedBlock { .. } => {

231

                // Soft wrap opportunity before the atomic inline

232

                nodes.push(LayoutNode::Penalty {

233

                    item: None,

234

                    width: 0.0,

235

                    penalty: 0.0,

236

});

237

                nodes.push(LayoutNode::Box(

238

                    item.clone(),

239

                    get_item_measure(item, is_vertical),

240

));

241

                // Soft wrap opportunity after the atomic inline

242

                nodes.push(LayoutNode::Penalty {

243

                    item: None,

244

                    width: 0.0,

245

                    penalty: 0.0,

246

});

247

248

            ShapedItem::Tab { bounds, .. } => {

249

                nodes.push(LayoutNode::Glue {

250

                    item: item.clone(),

251

                    width: bounds.width,

252

                    stretch: bounds.width * 0.5, // Treat like a space for flexibility

253

                    shrink: bounds.width * 0.33,

254

});

255

256

            ShapedItem::Break { .. } => {

257

                nodes.push(LayoutNode::Penalty {

258

                    item: None,

259

                    width: 0.0,

260

                    penalty: -INFINITY_BADNESS,

261

});

262

263

264

265

266

    nodes

267

268

269

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

270

fn find_optimal_breakpoints(nodes: &[LayoutNode], constraints: &UnifiedConstraints) -> Vec<usize> {

271

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

272

//

273

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

274

    // For MinContent, we also use a large value but will break at every word boundary.

275

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

276

277

    let line_width = match constraints.available_width {

278

        AvailableSpace::Definite(w) => w,

279

        AvailableSpace::MaxContent => f32::MAX / 2.0,

280

        // For MinContent: use a large width and let the greedy line breaker

281

        // break after each word. We DON'T use 0.0 because that breaks after

282

        // every character (including mid-word).

283

        AvailableSpace::MinContent => f32::MAX / 2.0,

284

};

285

286

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

287

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

288

    let text_indent = constraints.text_indent;

289

    let first_line_width = if !constraints.text_indent_hanging {

290

        line_width - text_indent

291

    } else {

292

        line_width

293

};

294

    let non_first_line_width = if constraints.text_indent_hanging {

295

        line_width - text_indent

296

    } else {

297

        line_width

298

};

299

300

    let mut breakpoints = vec![

301

        Breakpoint {

302

            demerit: INFINITY_BADNESS,

303

            previous: 0,

304

            line: 0

305

};

306

        nodes.len() + 1

307

];

308

    breakpoints[0] = Breakpoint {

309

        demerit: 0.0,

310

        previous: 0,

311

        line: 0,

312

};

313

314

    for i in 0..nodes.len() {

315

        // Optimization:

316

//

317

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

318

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

319

320

        if !matches!(nodes.get(i), Some(LayoutNode::Penalty { .. })) {

321

            continue;

322

323

324

        for j in (0..=i).rev() {

325

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

326

            let (mut current_width, mut stretch, mut shrink) = (0.0, 0.0, 0.0);

327

328

            for k in j..=i {

329

                match &nodes[k] {

330

                    LayoutNode::Box(_, w) => current_width += w,

331

                    LayoutNode::Glue {

332

                        width,

333

                        stretch: s,

334

                        shrink: k,

335

..

336

                    } => {

337

                        current_width += width;

338

                        stretch += s;

339

                        shrink += k;

340

341

                    LayoutNode::Penalty { width, .. } => current_width += width,

342

343

344

345

            let effective_line_width = if breakpoints[j].line == 0 {

346

                first_line_width

347

            } else if constraints.text_indent_hanging {

348

                non_first_line_width

349

            } else {

350

                line_width

351

};

352

353

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

354

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

355

            let ratio = if current_width < effective_line_width {

356

                if stretch > 0.0 {

357

                    (effective_line_width - current_width) / stretch

358

                } else {

359

                    INFINITY_BADNESS // Cannot stretch

360

361

            } else if current_width > effective_line_width {

362

                if shrink > 0.0 {

363

                    (effective_line_width - current_width) / shrink

364

                } else {

365

                    INFINITY_BADNESS // Cannot shrink

366

367

            } else {

368

                0.0 // Perfect fit

369

};

370

371

            // Lines that must shrink too much are invalid.

372

            if ratio < -1.0 {

373

                continue;

374

375

376

            // Calculate badness

377

            let mut badness = 100.0 * ratio.abs().powi(3);

378

379

            // Add penalty for the break point

380

            if let Some(LayoutNode::Penalty { penalty, .. }) = nodes.get(i) {

381

                if *penalty >= 0.0 {

382

                    badness += penalty;

383

                } else if *penalty <= -INFINITY_BADNESS {

384

                    badness = -INFINITY_BADNESS; // Forced break

385

386

387

388

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

389

            // ratios (fitness classes).

390

//

391

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

392

            let demerit = badness + breakpoints[j].demerit;

393

394

            if demerit < breakpoints[i + 1].demerit {

395

                breakpoints[i + 1] = Breakpoint {

396

                    demerit,

397

                    previous: j,

398

                    line: breakpoints[j].line + 1,

399

};

400

401

402

403

404

    // Backtrack from the end to find the break points

405

    let mut breaks = Vec::new();

406

    let mut current = nodes.len();

407

    while current > 0 {

408

        breaks.push(current);

409

        let prev_idx = breakpoints[current].previous;

410

        current = prev_idx;

411

412

    breaks.reverse();

413

    breaks

414

415

416

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

417

fn position_lines_from_breaks(

418

    nodes: &[LayoutNode],

419

    breaks: &[usize],

420

    logical_items: &[LogicalItem],

421

    constraints: &UnifiedConstraints,

422

) -> UnifiedLayout {

423

    let mut positioned_items = Vec::new();

424

    let mut start_node = 0;

425

    let mut cross_axis_pen = 0.0;

426

    let base_direction = get_base_direction_from_logical(logical_items);

427

    for (line_index, &end_node) in breaks.iter().enumerate() {

428

        let line_nodes = &nodes[start_node..end_node];

429

        let is_last_line = line_index == breaks.len() - 1;

430

431

        let line_items: Vec<ShapedItem> = line_nodes

432

            .iter()

433

            .filter_map(|node| match node {

434

                LayoutNode::Box(item, _) => Some(item.clone()),

435

                LayoutNode::Glue { item, .. } => Some(item.clone()),

436

                LayoutNode::Penalty { item, .. } => item.clone(),

437

})

438

            .collect();

439

440

        // Note: Calculate spacing, do not mutate items

441

        let mut extra_per_space = 0.0;

442

        let line_width: f32 = line_items.iter().map(|i| get_item_measure(i, false)).sum();

443

444

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

445

        let ends_with_forced_break = line_nodes.iter().any(|n| matches!(

446

            n, LayoutNode::Penalty { penalty, .. } if *penalty <= -INFINITY_BADNESS

447

));

448

        let effective_align = super::cache::resolve_effective_alignment(

449

            constraints.text_align,

450

            constraints.text_align_last,

451

            is_last_line || ends_with_forced_break,

452

);

453

454

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

455

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

456

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

457

        let should_justify = constraints.text_justify != JustifyContent::None

458

            && (!is_last_line || constraints.text_align == TextAlign::JustifyAll

459

                || effective_align == TextAlign::Justify || effective_align == TextAlign::JustifyAll);

460

461

        // Get the available width as f32 for calculations

462

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

463

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

464

        let available_width_f32 = match constraints.available_width {

465

            AvailableSpace::Definite(w) => w,

466

            AvailableSpace::MaxContent => line_width,

467

            AvailableSpace::MinContent => line_width,

468

};

469

470

        if should_justify {

471

            let space_to_add = available_width_f32 - line_width;

472

            if space_to_add > 0.0 {

473

                let space_count = line_items

474

                    .iter()

475

                    .filter(|item| is_word_separator(item))

476

                    .count();

477

                if space_count > 0 {

478

                    extra_per_space = space_to_add / space_count as f32;

479

480

481

482

483

        // Alignment & Positioning

484

        let total_width: f32 = line_items

485

            .iter()

486

            .map(|item| get_item_measure(item, false))

487

            .sum();

488

489

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

490

        let is_indefinite = matches!(

491

            constraints.available_width,

492

            AvailableSpace::MaxContent | AvailableSpace::MinContent

493

);

494

        let remaining_space = if is_indefinite {

495

0.0

496

        } else {

497

            available_width_f32

498

                - (total_width

499

                    + extra_per_space

500

                        * line_items

501

                            .iter()

502

                            .filter(|item| is_word_separator(item))

503

                            .count() as f32)

504

};

505

506

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

507

        let physical_align = match (effective_align, base_direction) {

508

            (TextAlign::Start, BidiDirection::Ltr) => TextAlign::Left,

509

            (TextAlign::Start, BidiDirection::Rtl) => TextAlign::Right,

510

            (TextAlign::End, BidiDirection::Ltr) => TextAlign::Right,

511

            (TextAlign::End, BidiDirection::Rtl) => TextAlign::Left,

512

            (other, _) => other,

513

};

514

515

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

516

        let mut main_axis_pen = if remaining_space < 0.0 {

517

0.0

518

        } else {

519

            match physical_align {

520

                TextAlign::Center => remaining_space / 2.0,

521

                TextAlign::Right => remaining_space,

522

                _ => 0.0,

523

524

};

525

526

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

527

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

528

        if constraints.text_indent != 0.0 {

529

            let is_indent_target = if constraints.text_indent_each_line {

530

                line_index == 0 // TODO: also detect lines after forced breaks in KP path

531

            } else {

532

                line_index == 0

533

};

534

            let should_indent = if constraints.text_indent_hanging {

535

                !is_indent_target

536

            } else {

537

                is_indent_target

538

};

539

            if should_indent {

540

                main_axis_pen += constraints.text_indent;

541

542

543

544

        for item in line_items {

545

            let item_advance = get_item_measure(&item, false);

546

547

            let draw_pos = match &item {

548

                ShapedItem::Cluster(c) if !c.glyphs.is_empty() => {

549

                    let glyph = &c.glyphs[0];

550

                    Point {

551

                        x: main_axis_pen + glyph.offset.x,

552

                        y: cross_axis_pen - glyph.offset.y, // Use - for GPOS offset

553

554

555

                _ => Point {

556

                    x: main_axis_pen,

557

                    y: cross_axis_pen,

558

},

559

};

560

561

            positioned_items.push(PositionedItem {

562

                item: item.clone(),

563

                position: draw_pos,

564

                line_index,

565

});

566

567

            main_axis_pen += item_advance;

568

569

            // Apply extra spacing to the pen

570

            if is_word_separator(&item) {

571

                main_axis_pen += extra_per_space;

572

573

574

575

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

576

        cross_axis_pen += constraints.resolved_line_height();

577

        start_node = end_node;

578

579

580

    UnifiedLayout {

581

        items: positioned_items,

582

        overflow: OverflowInfo::default(),

583

584