path: root/crates/fmt/src/linebreak.rs

// yt - A fully featured command line YouTube client
//
// Copyright (C) 2025 Benedikt Peetz <benedikt.peetz@b-peetz.de>
// Copyright (C) 2025 uutils developers
// SPDX-License-Identifier: MIT
//
// This file is part of Yt.
//
// You should have received a copy of the License along with this program.
// If not, see <https://www.gnu.org/licenses/gpl-3.0.txt>.

// This file is part of the uutils coreutils package.
//
// For the full copyright and license information, please view the LICENSE
// file that was distributed with this source code.

use std::fmt::Write;
use std::{cmp, mem};

use crate::FmtOptions;
use crate::parasplit::{ParaWords, Paragraph, WordInfo};

struct BreakArgs<'a> {
    opts: &'a FmtOptions,
    init_len: usize,
    indent_str: &'a str,
    indent_len: usize,
    uniform: bool,
    output: String,
}

impl BreakArgs<'_> {
    fn compute_width(&self, winfo: &WordInfo<'_>, position_n: usize, fresh: bool) -> usize {
        if fresh {
            0
        } else {
            let post = winfo.after_tab;
            match winfo.before_tab {
                None => post,
                Some(pre) => {
                    post + ((pre + position_n) / self.opts.tabwidth + 1) * self.opts.tabwidth
                        - position_n
                }
            }
        }
    }
}

pub(super) fn break_lines(para: &Paragraph, opts: &FmtOptions) -> String {
    let mut output = String::new();

    // indent
    let p_indent = &para.indent_str;
    let p_indent_len = para.indent_len;

    // words
    let p_words = ParaWords::new(opts, para);
    let mut p_words_words = p_words.words();

    // the first word will *always* appear on the first line
    // make sure of this here
    let Some(winfo) = p_words_words.next() else {
        return "\n".to_owned();
    };

    // print the init, if it exists, and get its length
    let p_init_len = winfo.word_nchars
        + if opts.crown_margin || opts.tagged_paragraph {
            // handle "init" portion
            output.push_str(&para.init_str);
            para.init_len
        } else if !para.mail_header {
            // for non-(crown, tagged) that's the same as a normal indent
            output.push_str(p_indent);
            p_indent_len
        } else {
            // except that mail headers get no indent at all
            0
        };

    // write first word after writing init
    write!(output, "{}", winfo.word).expect("Works");

    // does this paragraph require uniform spacing?
    let uniform = para.mail_header || opts.uniform;

    let mut break_args = BreakArgs {
        opts,
        init_len: p_init_len,
        indent_str: p_indent,
        indent_len: p_indent_len,
        uniform,
        output,
    };

    if opts.quick || para.mail_header {
        break_simple(p_words_words, &mut break_args);
    } else {
        break_knuth_plass(p_words_words, &mut break_args);
    };

    break_args.output
}

// break_simple implements a "greedy" breaking algorithm: print words until
// maxlength would be exceeded, then print a linebreak and indent and continue.
fn break_simple<'a, T: Iterator<Item = &'a WordInfo<'a>>>(iter: T, args: &mut BreakArgs<'a>) {
    iter.fold((args.init_len, false), |(l, prev_punct), winfo| {
        accum_words_simple(args, l, prev_punct, winfo)
    });
    args.output.push('\n');
}

fn accum_words_simple<'a>(
    args: &mut BreakArgs<'a>,
    l: usize,
    prev_punct: bool,
    winfo: &'a WordInfo<'a>,
) -> (usize, bool) {
    // compute the length of this word, considering how tabs will expand at this position on the line
    let wlen = winfo.word_nchars + args.compute_width(winfo, l, false);

    let slen = compute_slen(
        args.uniform,
        winfo.new_line,
        winfo.sentence_start,
        prev_punct,
    );

    if l + wlen + slen > args.opts.width {
        write_newline(args.indent_str, &mut args.output);
        write_with_spaces(&winfo.word[winfo.word_start..], 0, &mut args.output);
        (args.indent_len + winfo.word_nchars, winfo.ends_punct)
    } else {
        write_with_spaces(winfo.word, slen, &mut args.output);
        (l + wlen + slen, winfo.ends_punct)
    }
}

// break_knuth_plass implements an "optimal" breaking algorithm in the style of
//    Knuth, D.E., and Plass, M.F. "Breaking Paragraphs into Lines." in Software,
//    Practice and Experience. Vol. 11, No. 11, November 1981.
//    http://onlinelibrary.wiley.com/doi/10.1002/spe.4380111102/pdf
#[allow(trivial_casts)]
fn break_knuth_plass<'a, T: Clone + Iterator<Item = &'a WordInfo<'a>>>(
    mut iter: T,
    args: &mut BreakArgs<'a>,
) {
    // run the algorithm to get the breakpoints
    let breakpoints = find_kp_breakpoints(iter.clone(), args);

    // iterate through the breakpoints (note that breakpoints is in reverse break order, so we .rev() it
    let result: (bool, bool) = breakpoints.iter().rev().fold(
        (false, false),
        |(mut prev_punct, mut fresh), &(next_break, break_before)| {
            if fresh {
                write_newline(args.indent_str, &mut args.output);
            }
            // at each breakpoint, keep emitting words until we find the word matching this breakpoint
            for winfo in &mut iter {
                let (slen, word) = slice_if_fresh(
                    fresh,
                    winfo.word,
                    winfo.word_start,
                    args.uniform,
                    winfo.new_line,
                    winfo.sentence_start,
                    prev_punct,
                );
                fresh = false;
                prev_punct = winfo.ends_punct;

                // We find identical breakpoints here by comparing addresses of the references.
                // This is OK because the backing vector is not mutating once we are linebreaking.
                let winfo_ptr = winfo as *const _;
                let next_break_ptr = next_break as *const _;
                if winfo_ptr == next_break_ptr {
                    // OK, we found the matching word
                    if break_before {
                        write_newline(args.indent_str, &mut args.output);
                        write_with_spaces(&winfo.word[winfo.word_start..], 0, &mut args.output);
                    } else {
                        // breaking after this word, so that means "fresh" is true for the next iteration
                        write_with_spaces(word, slen, &mut args.output);
                        fresh = true;
                    }
                    break;
                }
                write_with_spaces(word, slen, &mut args.output);
            }
            (prev_punct, fresh)
        },
    );
    let (mut prev_punct, mut fresh) = result;

    // after the last linebreak, write out the rest of the final line.
    for winfo in iter {
        if fresh {
            write_newline(args.indent_str, &mut args.output);
        }
        let (slen, word) = slice_if_fresh(
            fresh,
            winfo.word,
            winfo.word_start,
            args.uniform,
            winfo.new_line,
            winfo.sentence_start,
            prev_punct,
        );
        prev_punct = winfo.ends_punct;
        fresh = false;
        write_with_spaces(word, slen, &mut args.output);
    }

    args.output.push('\n');
}

struct LineBreak<'a> {
    prev: usize,
    linebreak: Option<&'a WordInfo<'a>>,
    break_before: bool,
    demerits: i64,
    prev_rat: f32,
    length: usize,
    fresh: bool,
}

#[allow(clippy::cognitive_complexity)]
#[allow(clippy::cast_possible_wrap)]
fn find_kp_breakpoints<'a, T: Iterator<Item = &'a WordInfo<'a>>>(
    iter: T,
    args: &BreakArgs<'a>,
) -> Vec<(&'a WordInfo<'a>, bool)> {
    let mut iter = iter.peekable();
    // set up the initial null linebreak
    let mut linebreaks = vec![LineBreak {
        prev: 0,
        linebreak: None,
        break_before: false,
        demerits: 0,
        prev_rat: 0.0,
        length: args.init_len,
        fresh: false,
    }];
    // this vec holds the current active linebreaks; next_ holds the breaks that will be active for
    // the next word
    let mut active_breaks = vec![0];
    let mut next_active_breaks = vec![];

    let stretch = args.opts.width - args.opts.goal;
    let minlength = args.opts.goal.max(stretch + 1) - stretch;
    let mut new_linebreaks = vec![];
    let mut is_sentence_start = false;
    let mut least_demerits = 0;
    loop {
        let Some(w) = iter.next() else { break };

        // if this is the last word, we don't add additional demerits for this break
        let (is_last_word, is_sentence_end) = match iter.peek() {
            None => (true, true),
            Some(&&WordInfo {
                sentence_start: st,
                new_line: nl,
                ..
            }) => (false, st || (nl && w.ends_punct)),
        };

        // should we be adding extra space at the beginning of the next sentence?
        let slen = compute_slen(args.uniform, w.new_line, is_sentence_start, false);

        let mut ld_new = i64::MAX;
        let mut ld_next = i64::MAX;
        let mut ld_idx = 0;
        new_linebreaks.clear();
        next_active_breaks.clear();
        // go through each active break, extending it and possibly adding a new active
        // break if we are above the minimum required length
        #[allow(clippy::explicit_iter_loop)]
        for &i in active_breaks.iter() {
            let active = &mut linebreaks[i];
            // normalize demerits to avoid overflow, and record if this is the least
            active.demerits -= least_demerits;
            if active.demerits < ld_next {
                ld_next = active.demerits;
                ld_idx = i;
            }

            // get the new length
            let tlen = w.word_nchars
                + args.compute_width(w, active.length, active.fresh)
                + slen
                + active.length;

            // if tlen is longer than args.opts.width, we drop this break from the active list
            // otherwise, we extend the break, and possibly add a new break at this point
            if tlen <= args.opts.width {
                // this break will still be active next time
                next_active_breaks.push(i);
                // we can put this word on this line
                active.fresh = false;
                active.length = tlen;

                // if we're above the minlength, we can also consider breaking here
                if tlen >= minlength {
                    let (new_demerits, new_ratio) = if is_last_word {
                        // there is no penalty for the final line's length
                        (0, 0.0)
                    } else {
                        compute_demerits(
                            args.opts.goal as isize - tlen as isize,
                            stretch,
                            w.word_nchars,
                            active.prev_rat,
                        )
                    };

                    // do not even consider adding a line that has too many demerits
                    // also, try to detect overflow by checking signum
                    let total_demerits = new_demerits + active.demerits;
                    if new_demerits < BAD_INFTY_SQ
                        && total_demerits < ld_new
                        && active.demerits.signum() <= new_demerits.signum()
                    {
                        ld_new = total_demerits;
                        new_linebreaks.push(LineBreak {
                            prev: i,
                            linebreak: Some(w),
                            break_before: false,
                            demerits: total_demerits,
                            prev_rat: new_ratio,
                            length: args.indent_len,
                            fresh: true,
                        });
                    }
                }
            }
        }

        // if we generated any new linebreaks, add the last one to the list
        // the last one is always the best because we don't add to new_linebreaks unless
        // it's better than the best one so far
        match new_linebreaks.pop() {
            None => (),
            Some(lb) => {
                next_active_breaks.push(linebreaks.len());
                linebreaks.push(lb);
            }
        }

        if next_active_breaks.is_empty() {
            // every potential linebreak is too long! choose the linebreak with the least demerits, ld_idx
            let new_break =
                restart_active_breaks(args, &linebreaks[ld_idx], ld_idx, w, slen, minlength);
            next_active_breaks.push(linebreaks.len());
            linebreaks.push(new_break);
            least_demerits = 0;
        } else {
            // next time around, normalize out the demerits fields
            // on active linebreaks to make overflow less likely
            least_demerits = cmp::max(ld_next, 0);
        }
        // swap in new list of active breaks
        mem::swap(&mut active_breaks, &mut next_active_breaks);
        // If this was the last word in a sentence, the next one must be the first in the next.
        is_sentence_start = is_sentence_end;
    }

    // return the best path
    build_best_path(&linebreaks, &active_breaks)
}

fn build_best_path<'a>(paths: &[LineBreak<'a>], active: &[usize]) -> Vec<(&'a WordInfo<'a>, bool)> {
    // of the active paths, we select the one with the fewest demerits
    active
        .iter()
        .min_by_key(|&&a| paths[a].demerits)
        .map(|&(mut best_idx)| {
            let mut breakwords = vec![];
            // now, chase the pointers back through the break list, recording
            // the words at which we should break
            loop {
                let next_best = &paths[best_idx];
                match next_best.linebreak {
                    None => return breakwords,
                    Some(prev) => {
                        breakwords.push((prev, next_best.break_before));
                        best_idx = next_best.prev;
                    }
                }
            }
        })
        .unwrap_or_default()
}

// "infinite" badness is more like (1+BAD_INFTY)^2 because of how demerits are computed
const BAD_INFTY: i64 = 10_000_000;
const BAD_INFTY_SQ: i64 = BAD_INFTY * BAD_INFTY;
// badness = BAD_MULT * abs(r) ^ 3
const BAD_MULT: f32 = 100.0;
// DR_MULT is multiplier for delta-R between lines
const DR_MULT: f32 = 600.0;
// DL_MULT is penalty multiplier for short words at end of line
const DL_MULT: f32 = 300.0;

#[allow(clippy::cast_precision_loss)]
#[allow(clippy::cast_possible_truncation)]
fn compute_demerits(delta_len: isize, stretch: usize, wlen: usize, prev_rat: f32) -> (i64, f32) {
    // how much stretch are we using?
    let ratio = if delta_len == 0 {
        0.0f32
    } else {
        delta_len as f32 / stretch as f32
    };

    // compute badness given the stretch ratio
    let bad_linelen = if ratio.abs() > 1.0f32 {
        BAD_INFTY
    } else {
        (BAD_MULT * ratio.powi(3).abs()) as i64
    };

    // we penalize lines ending in really short words
    let bad_wordlen = if wlen >= stretch {
        0
    } else {
        (DL_MULT
            * ((stretch - wlen) as f32 / (stretch - 1) as f32)
                .powi(3)
                .abs()) as i64
    };

    // we penalize lines that have very different ratios from previous lines
    let bad_delta_r = (DR_MULT * ((ratio - prev_rat) / 2.0).powi(3).abs()) as i64;

    let demerits = i64::pow(1 + bad_linelen + bad_wordlen + bad_delta_r, 2);

    (demerits, ratio)
}

#[allow(clippy::cast_possible_wrap)]
fn restart_active_breaks<'a>(
    args: &BreakArgs<'a>,
    active: &LineBreak<'a>,
    act_idx: usize,
    w: &'a WordInfo<'a>,
    slen: usize,
    min: usize,
) -> LineBreak<'a> {
    let (break_before, line_length) = if active.fresh {
        // never break before a word if that word would be the first on a line
        (false, args.indent_len)
    } else {
        // choose the lesser evil: breaking too early, or breaking too late
        let wlen = w.word_nchars + args.compute_width(w, active.length, active.fresh);
        let underlen = min as isize - active.length as isize;
        let overlen = (wlen + slen + active.length) as isize - args.opts.width as isize;
        if overlen > underlen {
            // break early, put this word on the next line
            (true, args.indent_len + w.word_nchars)
        } else {
            (false, args.indent_len)
        }
    };

    // restart the linebreak. This will be our only active path.
    LineBreak {
        prev: act_idx,
        linebreak: Some(w),
        break_before,
        demerits: 0, // this is the only active break, so we can reset the demerit count
        prev_rat: if break_before { 1.0 } else { -1.0 },
        length: line_length,
        fresh: !break_before,
    }
}

// Number of spaces to add before a word, based on mode, newline, sentence start.
#[allow(clippy::fn_params_excessive_bools)]
fn compute_slen(uniform: bool, newline: bool, start: bool, punct: bool) -> usize {
    if uniform || newline {
        if start || (newline && punct) { 2 } else { 1 }
    } else {
        0
    }
}

// If we're on a fresh line, slen=0 and we slice off leading whitespace.
// Otherwise, compute slen and leave whitespace alone.
#[allow(clippy::fn_params_excessive_bools)]
fn slice_if_fresh(
    fresh: bool,
    word: &str,
    start: usize,
    uniform: bool,
    newline: bool,
    second_start: bool,
    punct: bool,
) -> (usize, &str) {
    if fresh {
        (0, &word[start..])
    } else {
        (compute_slen(uniform, newline, second_start, punct), word)
    }
}

// Write a newline and add the indent.
fn write_newline(indent: &str, output: &mut String) {
    output.push('\n');
    output.push_str(indent);
}

// Write the word, along with slen spaces.
fn write_with_spaces(word: &str, slen: usize, output: &mut String) {
    if slen == 2 {
        output.push_str("  ");
    } else if slen == 1 {
        output.push(' ');
    }
    output.push_str(word);
}