Very rough WIP line breaking algorithm from skribo-layout

lib.rs

use xi_unicode::LineBreakIterator;

use skribo::{AdvanceWidth, FontCollection, LayoutSession};

pub struct LayoutBuilder {
    text: String,
    default_font: FontCollection,
    default_size: f64,
    max_width: f64,
}

pub struct Layout {
    text: String,
    layouts: Vec<LayoutSession<String>>,
    breaks: Vec<usize>,
}

impl LayoutBuilder {
    pub fn new(default_font: FontCollection, text: impl Into<String>) -> LayoutBuilder {
        let text = text.into();
        let default_size = 12.0;
        LayoutBuilder {
            text,
            default_font,
            default_size,
            max_width: f64::INFINITY,
        }
    }

    pub fn max_width(&mut self, max_width: f64) {
        self.max_width = max_width;
    }

    pub fn build(self) -> Layout {
        let mut layout = Layout {
            text: self.text,
            layouts: Vec::new(),
            breaks: Vec::new(),
        };
        layout.rewrap(self.max_width);
        layout
    }
}

impl Layout {
    /// Recompute the line breaks.
    fn rewrap(&mut self, max_width: f64) {
        // This function is complex. My apologies to anyone trying to read it, or, worse,
        // modify it. Let me try to explain.
        //
        // The line break iterator gives a sequence of candidate breaks. Basically,
        // this function chooses a subset of those breaks, with the following logic:
        //
        // * All hard breaks are selected.
        // * No lines are overfull.
        // * No lines are underfull.
        //
        // Now we'll define those last two terms. A line is a span between two positions
        // that are either start of text, end of text, or a chosen break. The width of the
        // line is the measured width of the substring from the line start to the line end,
        // trimmed of any trailing whitespace.
        //
        // An overfull line is one spanning more than one candidate break in which the
        // measured width is greater than the maximum width. Lines bounded by two consecutive
        // candidate breaks are allowed to be wider than the maximum width because there's
        // not much else you can do. (Android has "desperate breaks" which can cut a word
        // at grapheme boundaries, but we're opting not to do that)
        //
        // An underfull line is one where the ending break is soft, and extending the
        // line to end at the next candidate break would still not exceed the maximum
        // width. A blank line at the end is considered underfull unless it starts with a
        // hard break.
        //
        // The algorithm is more or less derived logically from the above requirements.
        // Most of the rest of the complexity comes from a desire to go through the layouts
        // in a single pass, measuring widths by considering line ends and a window of
        // two candidate line starts.
        self.breaks.clear();
        let mut cur_layout = 0;
        let mut layout_start = 0;
        // Width of substring from line_start to max(line_start, layout_start)
        let mut complete_width = 0.0;
        let mut last_good_break = None;
        // Width of substring from last_good_break to max(last_good_break, layout_start)
        let mut last_complete_width = 0.0;
        for (ix, is_hard) in LineBreakIterator::new(&self.text) {
            // Might need to consider a break (at most) twice.
            loop {
                let line_start = self.breaks.last().cloned().unwrap_or(0);
                // Note: this trims U+00A0 (NBSP), matching DWrite behavior.
                let trim_ix = line_start + self.text[line_start..ix].trim_end().len();
                // Invariant: line_start < last_good_break <= trim_ix <= ix

                // Determine the width of the line from the last break to
                // the proposed break.
                let line_width;
                loop {
                    if cur_layout == self.layouts.len() {
                        line_width = complete_width;
                        break;
                    }
                    let layout = &self.layouts[cur_layout];
                    let start_adv =
                        layout.cumulative_advance(line_start.saturating_sub(layout_start));
                    if trim_ix >= layout_start + layout.text_len() {
                        let layout_width = layout.width();
                        if line_start >= layout_start {
                            complete_width = layout_width - (start_adv as f64);
                        } else {
                            complete_width += layout_width;
                        }
                        if let Some(last_good_break) = last_good_break {
                            if last_good_break >= layout_start {
                                if last_good_break - layout_start < layout.text_len() {
                                    let lgb_adv =
                                        layout.cumulative_advance(last_good_break - layout_start);
                                    last_complete_width = layout_width - (lgb_adv as f64);
                                }
                            } else {
                                last_complete_width += layout_width;
                            }
                        }
                        layout_start += layout.text_len();
                        cur_layout += 1;
                    } else {
                        let end_adv = layout.cumulative_advance(trim_ix - layout_start);
                        // Note: this can be an approximation to the measured width of the substring,
                        // in the case of highly complex shaping. For now, choose speed and simplicity
                        // over accuracy.
                        line_width = (end_adv - start_adv) as f64 + complete_width;
                        break;
                    }
                }
                // Invariant restored: layout_start <= trim_ix < layout_start + layout.text_len()
                if line_width > max_width {
                    if let Some(last_good_break) = last_good_break.take() {
                        self.breaks.push(last_good_break);
                        complete_width = last_complete_width;
                    // consider break again
                    } else {
                        if is_hard || ix < self.text.len() {
                            self.breaks.push(ix);
                            complete_width = 0.0;
                        }
                        break;
                    }
                } else if is_hard {
                    self.breaks.push(ix);
                    complete_width = 0.0;
                    last_good_break = None;
                    break;
                } else {
                    last_good_break = Some(ix);
                    last_complete_width = 0.0;
                    break;
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn it_works() {
        assert_eq!(2 + 2, 4);
    }
}