pretty_expressive/

cost.rs

use std::{fmt, ops::Add};

/// A measurement of the badness of a particular printing layout.
///
/// [`Doc`](crate::Doc) is generic on the `Cost` type it can be used with, since
/// a document can contain [`cost`](crate::cost) nodes that increase the cost of
/// certain paths.
///
/// When a document is being printed, costs are assigned
/// by a [`CostFactory`]. This determines the badness of
/// [`text`](crate::text)/[`newline`](crate::newline) nodes based on their
/// location in the layout. The printer will then try to minimize this cost
/// overall.
///
/// A [`DefaultCost`] and [`DefaultCostFactory`] is provided, and
/// [`Doc`](crate::Doc) will default to using the `DefaultCost` if no generic
/// parameter is given to it.
///
/// ## Requirements for costs
///
/// A `Cost` must satisfy several properties for the printer to be able to use
/// it correctly:
///
/// * `a <= b` must be a total order. This requirement is imposed by the [`Ord`]
///   trait.
/// * `a + b` (via the [`Add`] trait) must be commutative and associative.
/// * If `a <= b` and `c <= d`, then `a + c <= b + d`.
///
/// There are [additional
/// requirements](CostFactory#requirements-for-cost-factories) for the functions
/// on the [`CostFactory`].
pub trait Cost: Ord + Add + Clone + fmt::Debug {}

/// Trait for types that can assign costs to particular layouts of a document.
///
/// A custom cost factory can be used with
/// [`validate_with_cost`](crate::Doc::validate_with_cost) to customize how the
/// costs of different layouts are determined.
///
/// In most cases, the [`DefaultCostFactory`] that is used by `to_string()` and
/// [`validate`](crate::Doc::validate) will be sufficient.
///
/// ## Requirements for cost factories
///
/// In addition to the [requirements](Cost#requirements-for-costs) imposed on
/// the [`Cost`] type itself, a cost factory's operation must satisfy certain
/// properties for the printer to behave correctly:
///
/// * If `c1 <= c2`, then `text(c1, l) <= text(c2, l)`: the cost of adding the
///   same length of text must not decrease as the column moves to the right.
/// * If `i1 <= i2`, then `newline(i1) <= newline(i2)`: the cost of adding a
///   newline must not decrease as the indentation level increases.
/// * `text(c, l1) + text(c + l1, l2) == text(c, l1 + l2)`: splitting or
///   combining text at the same position must not affect its cost.
pub trait CostFactory: fmt::Debug {
    /// The type of cost values that the factory will assign.
    type CostType: Cost<Output = Self::CostType>;

    /// Determine the cost of adding a slice of text to the document.
    ///
    /// The text being added has length `l` and begins at column `c`.
    fn text(&self, c: usize, l: usize) -> Self::CostType;

    /// Determine the cost of adding a newline to the document.
    ///
    /// There will be `i` spaces of indentation included after the newline.
    fn newline(&self, i: usize) -> Self::CostType;

    /// The computation width limit.
    ///
    /// If a layout the printer is attempting will exceed this width for a line,
    /// the printer will consider that layout "tainted". A tainted layout will
    /// not be rejected outright. Instead, it will be set aside in case there
    /// are no valid untainted layouts. In that case, a tainted layout might be
    /// chosen, but it is not guaranteed to be the optimal one.
    fn limit(&self) -> usize;
}

/// The default strategy for assigning costs to layouts.
///
/// This cost factory uses [`DefaultCost`] as its cost type. Its documentation
/// has more information about the components that make up the cost.
///
/// The default cost factory has two configurable parameters:
///
/// * `page_width`: Required. The desired width of the document. Layouts that
///   exceed this width will have a cost imposed based on how much they exceed
///   it. The printer will choose a layout that fits within this width unless it
///   is not possible to do so.
/// * `computation_width`: Optional. A more extreme width constraint. Documents
///   that extend beyond this width will be "tainted", and will not be explored
///   further by the printer until it exhausts all untainted options. This
///   constraint improves the performance of the printer. If not provided, it
///   will default to `1.2 * page_width`.
///
/// This cost factory is used in the following situations:
///
/// * Calling `to_string()` on a [Doc](crate::Doc) will use this cost factory
///   with a page width of 80.
/// * Formatting a [Doc](crate::Doc) using one of [Rust's formatting
///   macros](std::fmt#related-macros) will use this cost factory. If a width
///   parameter is given to the macro, it will be used as the page width.
///   Otherwise, the default 80 characters will be used
/// * Calling [`Doc::validate`](crate::Doc::validate) will use this cost factory
///   with the given page width.
///
/// None of these allow overriding the computation width,
/// as it isn't usually necessary. If you want to use a
/// custom computation width, you can use [`Self::new`] and
/// [`Doc::validate_with_cost`](crate::Doc::validate_with_cost).
#[derive(Debug)]
pub struct DefaultCostFactory {
    page_width: usize,
    computation_width: Option<usize>,
}

/// The default cost type used for documents.
///
/// It is composed of two values: the badness and the number of newlines. The
/// badness quantifies how much the layout overflows the desired page width.
/// When this cost is used, the badness will be minimized first, then the number
/// of newlines will be minimized from there.
///
/// This cost is generally used with the [`DefaultCostFactory`], but it is valid
/// to use it with a custom cost factory if it serves your needs.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct DefaultCost(
    /// The badness of the layout.
    pub i32,
    /// The number of newlines the layout produced.
    pub i32,
);

impl DefaultCostFactory {
    /// Create a new cost factory with the given parameters.
    pub fn new(page_width: usize, computation_width: Option<usize>) -> Self {
        Self {
            page_width,
            computation_width,
        }
    }
}

impl CostFactory for DefaultCostFactory {
    type CostType = DefaultCost;

    /// Adds 1 to the [second component](DefaultCost::1) of the cost.
    ///
    /// The indentation level is ignored in this cost factory.
    fn newline(&self, _i: usize) -> Self::CostType {
        DefaultCost(0, 1)
    }

    /// Adds to the [first component](DefaultCost::0) of the cost if the page
    /// width is exceeded.
    ///
    /// If the text will not exceed the page width, no cost is imposed.
    fn text(&self, c: usize, l: usize) -> Self::CostType {
        let stop = c + l;
        if stop > self.page_width {
            let maxwc = self.page_width.max(c) as i32;
            let a = maxwc - (self.page_width as i32);
            let b = (stop as i32) - maxwc;
            DefaultCost(b * (2 * a + b), 0)
        } else {
            DefaultCost(0, 0)
        }
    }

    fn limit(&self) -> usize {
        match self.computation_width {
            None => (1.2 * (self.page_width as f64)) as usize,
            Some(cw) => cw,
        }
    }
}

impl Add for DefaultCost {
    type Output = Self;

    /// Pair-wise adds the individual components of the cost.
    fn add(self, rhs: Self) -> Self::Output {
        Self(self.0 + rhs.0, self.1 + rhs.1)
    }
}

impl Cost for DefaultCost {}