pretty_expressive/

lib.rs

#![deny(missing_docs)]
#![deny(rustdoc::broken_intra_doc_links)]
#![deny(rustdoc::unescaped_backticks)]

//! This crate is a Rust port of the [pretty-expressive][] printer from Racket.
//! It is an efficient pretty printer with an expressive language for describing
//! documents. The algorithm is described in ["A Pretty Expressive Printer"][paper].
//! The two official implementations, in [Racket][racket-impl] and [OCaml][ocaml-impl],
//! were both instrumental to being able to port the library to Rust.
//!
//! [pretty-expressive]: https://docs.racket-lang.org/pretty-expressive/
//! [paper]: https://dl.acm.org/doi/abs/10.1145/3622837
//! [racket-impl]: https://github.com/sorawee/pretty-expressive
//! [ocaml-impl]: https://github.com/sorawee/pretty-expressive-ocaml
//!
//! # Overview
//!
//! To use the pretty printer, you need to construct an "abstract document" (a [`Doc`] in
//! this library). This document contains not just the text you want to format, but also
//! instructions about the different ways that it is valid to format it. `pretty-expressive`
//! provides a variety of functions and operators to help you construct these documents.
//!
//! Let's look at a small example:
//!
//! ```
//! # use pretty_expressive::*;
//! let then_expr = text("'even");
//! let else_expr = text("'odd");
//! let cond_expr = text("(zero? (mod n 2))");
//!
//! let one_line = cond_expr.clone() &
//!                space() &
//!                then_expr.clone() &
//!                space() &
//!                else_expr.clone();
//!
//! let one_column = align(cond_expr.clone() &
//!                        nl() &
//!                        then_expr.clone() &
//!                        nl() &
//!                        else_expr.clone());
//!
//! let if_expr = lparen() &
//!               text("if ") &
//!               (one_line | one_column) &
//!               rparen();
//!
//! let doc = lparen() &
//!           text("defn even? (n)") &
//!           nest(2, nl() & if_expr & rparen());
//!
//! # assert_eq!(doc.to_string(),
//! # r"(defn even? (n)
//! #   (if (zero? (mod n 2)) 'even 'odd))");
//! ```
//!
//! It may look overwhelming at first, but if you can look past all the `clone()`s, it's
//! expressing something pretty simple. This document contains the code to define a small
//! Lisp function to check if a number is even. To create the document:
//!
//! 1. The three inputs to the `if` expression are created with [`text`].
//! 2. We reuse those three documents to describe two different layouts for how those inputs
//!    could be formatted. One places all three on the same line, while the other aligns them
//!    vertically in a column. The [`&`](Doc::bitand) operator is used to concatenate the
//!    smaller documents together with punctuation into a larger document.
//! 3. The `if` expression combines the two layouts in one document using the [`|`](Doc::bitor)
//!    operator. This gives the printer a choice. It has to choose one of these two layouts
//!    to render for this portion of the document. The printer will decide which is more
//!    optimal and use that one.
//! 4. Finally, the final document is built by combining the if expression with other
//!    documents to describe the layout of the entire function definition. [`nest`] is used to
//!    indent the body of the `defn` (i.e. the `if` expression) by 2 spaces.
//!
//! Now that we've constructed the document, we can call `doc.to_string()` to render it to a
//! [`String`].
//!
//! ```
//! # use pretty_expressive::*;
//! # let then_expr = text("'even");
//! # let else_expr = text("'odd");
//! # let cond_expr = text("(zero? (mod n 2))");
//! #
//! # let if_expr = lparen() & text("if ") &
//! #     ((cond_expr.clone() & space() & then_expr.clone() &
//! #         space() & else_expr.clone()) |
//! #      align(cond_expr.clone() & nl() & then_expr.clone() &
//! #         nl() & else_expr.clone())) & rparen();
//! # let doc = lparen() & text("defn even? (n)") &
//! #     nest(2, nl() & if_expr & rparen());
//! assert_eq!(doc.to_string(),
//! r"(defn even? (n)
//!   (if (zero? (mod n 2)) 'even 'odd))");
//! ```
//!
//! The main constraint we can impose on the printer is the _page width_: the maximum number
//! of characters we want to fit on a single line. Calling `to_string()` uses a default page
//! width of 80 characters. If we want to use a different page width, we can use the [`format!`]
//! macro.
//!
//! Since there's plenty of room, the printer opted to put all three `if` arguments on one
//! line together. If we use a smaller page width, the printer makes a different choice:
//!
//! ```
//! # use pretty_expressive::*;
//! # let then_expr = text("'even");
//! # let else_expr = text("'odd");
//! # let cond_expr = text("(zero? (mod n 2))");
//! #
//! # let if_expr = lparen() & text("if ") &
//! #     ((cond_expr.clone() & space() & then_expr.clone() &
//! #         space() & else_expr.clone()) |
//! #      align(cond_expr.clone() & nl() & then_expr.clone() &
//! #         nl() & else_expr.clone())) & rparen();
//! # let doc = lparen() & text("defn even? (n)") &
//! #     nest(2, nl() & if_expr & rparen());
//! assert_eq!(format!("{doc:20}"),
//! r"(defn even? (n)
//!   (if (zero? (mod n 2))
//!       'even
//!       'odd))");
//! ```
//!
//! It might seem contrived to use a width so small: nobody would actually try to format
//! their code into a width of 20 characters! That's probably true, but imagine this
//! expression appears nested much further into a function, and further right in the line
//! it appears on. The document we created here describes the valid ways for this
//! expression to be formatted _no matter where in the overall document it appears_.
//!
//! This means we can write a Rust function that can describe how any `if` expression should
//! be formatted (this example isn't far off from doing so already). We can then do the same
//! for every possible construct in our language that needs formatting, composing them
//! together as needed. In the end, we have a program that can format any document in our
//! language, built from simple descriptions of the possible layouts each piece could use.
//!
//! # A more complete example
//!
//! I ported this library to Rust because I wanted to build a code formatter for MJL, a Lisp
//! language I'm creating. Other approaches I tried for solving the problem didn't get me the
//! results I was hoping for, and the code was much more convoluted. The [version I built with
//! `pretty-expressive`](https://git.midna.dev/mjm/mjl/src/branch/main/mjl-format/src/lib.rs)
//! handles more cases correctly and is significantly easier to read and reason about.
//!
//! # Creating abstract documents
//!
//! The documentation for [`Doc`] describes the different functions and operators used to
//! create, wrap, and combine abstract documents to prepare them to be printed.
//!
//! # Printing a document
//!
//! The example above used `to_string()` and [`format!`] to turn an abstract document into
//! a [`String`]. If you have another destination you want to write to, you can instead use
//! one of the other Rust formatting macros to send the printed document wherever you like.
//!
//! ```
//! # use pretty_expressive::*;
//!
//! let doc = text("hello world");
//! println!("{doc:120}");
//! ```
//!
//! You can use the [width](std::fmt#width) parameter in the macro to request a particular
//! page width.
//!
//! # Adjusting the printer's notion of "optimal"
//!
//! The pretty printer chooses an optimal layout by assigning a [`Cost`] to each layout it
//! explores. By default, it's designed to optimize first for not exceeding the desired page
//! width and second for minimizing the number of lines produced. In other words, it will
//! try to fit as much as it can on each line, only using more lines when it has no other
//! choice or it would make the document too wide.
//!
//! You can probably get pretty far using this default, but there are some ways to tweak it
//! if needed:
//!
//! * Use the [`cost`] function to increase the cost imposed on a particular document, which
//!   can cause the printer to choose an alternative layout instead.
//! * Replace the [`CostFactory`] that the printer uses to assign costs. If you do this, be
//!   sure to read the documentation carefully, as there are rules that costs and cost factories
//!   must follow for the printer to work correctly.
//!
//! # Credits
//!
//! My thanks to the authors of ["A Pretty Expressive Printer"][paper]:
//!
//! * Sorawee Porncharoenwase
//! * Justin Pombrio
//! * Emina Torlak
//!
//! This crate is almost entirely based on their ideas and using their implementations as a
//! reference.

mod cost;
mod measure;
mod non_empty;
mod print;

use std::{
    cell::Cell,
    collections::HashMap,
    ops::{BitAnd, BitOr},
    rc::Rc,
};

pub use cost::{Cost, CostFactory, DefaultCost, DefaultCostFactory};
pub use print::{Error, PrintResult, Result};

const MEMO_LIMIT: i8 = 7;
thread_local! {
    static GLOBAL_ID: Cell<usize> = const { Cell::new(0) };
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct DocId(usize);

/// An abstract document containing pretty printing instructions.
///
/// The `Doc` contains the tree of instructions and choices to present to the
/// pretty printer. The printer uses this information to choose an optimal
/// layout and produce it when asked.
///
/// A `Doc` is internally wrapped in an [`Rc`], so it is cheap to clone. It is
/// advantageous to `clone` and reuse a `Doc` when creating different choices
/// of layout for the same content, as this will save the printer from repeating
/// work. See the docs for [`|`](Self#sharing-subdocuments) for more
/// details on that.
///
/// # Constructing documents
///
/// Documents are constructed by starting with small pieces of text, which are
/// then wrapped and composed with various operators to describe constraints on
/// how they should be laid out by the printer.
///
/// ## Creating documents with content
///
/// The two basic atomic units of documents are:
///
/// * [`text`]: Renders some text verbatim
/// * [`newline`]: Moves the printer to the next line, possibly with indentation
///
/// All of the actual content in a document comes from these two functions or
/// convenience functions that wrap them.
///
/// ## Wrapping documents to modify behavior
///
/// There are also documents that wrap other documents to modify how they are
/// rendered by the printer:
///
/// * [`nest`]: Increases the indentation level for the document
/// * [`align`]: Aligns subsequent lines in the document to its starting column
/// * [`reset`]: Resets the indentation level to 0
/// * [`full`]: Requires the document to take up the remainder of its line
/// * [`cost`]: Artificially increase the cost of a document
///
/// Using these modifiers can help get exactly the desired layout with minimal
/// fuss.
///
/// ## Combining documents
///
/// Documents can be combined to create more complex ones using two operators:
///
/// * [`&`](Self::bitand): Concatenate documents to form a larger one
/// * [`|`](Self::bitor): Create a choice between two documents
///
/// These two operators are what enables the printer to optimally format complex
/// documents. Small documents can be combined into larger ones representing an
/// entire piece of text, and creating choices along the way gives the printer
/// options for different ways to format, allowing it to choose an optimal
/// layout.
///
/// # Printing documents
///
/// `Doc` implements [`Display`](std::fmt::Display), so they can be printed
/// in all the usual ways you expect to be able to print things in Rust. By
/// default, the doc will be constrained to a page width of 80 characters. If
/// you're using one of [Rust's formatting macros](std::fmt#related-macros),
/// then you can use a width parameter to customize this.
///
/// ## What if it fails to render?
///
/// Rendering a document can [`fail`]. Generally when this happens, it means
/// that you've put too tight of constraints on the choices given, so the
/// printer isn't able to find an option that is allowed. If you use `Doc`'s
/// implementation of [`Display`](std::fmt::Display) with a document that fails
/// to render, it will panic, as `Display` doesn't give a way to surface custom
/// errors. Usually, this is fine: correctly constructed documents for printing
/// should always have a valid choice path, even if some of the subdocuments
/// within do not.
///
/// If you want to be able to detect when a document has failed to print,
/// you can call [`doc.validate(page_width)`](Self::validate). This will run
/// the printer up to the point where it chooses a layout and return either
/// the layout chosen or an [`Error`]. The returned layout also implements
/// `Display`, so it can be printed from there. Note that since the page width
/// was chosen when `validate` was called (since it was needed for the printer
/// to choose the layout), the width cannot be customized in format macros when
/// printing a layout.
///
/// # Thread safety
///
/// Due to their use of [`Rc`] internally, `Doc`s cannot be moved from the thread
/// where they are created. They also use a thread-local static counter to assign
/// a unique ID to each `Doc`, so moving them between threads would also introduce
/// the possibility of collisions for these IDs.
#[derive(Debug)]
pub struct Doc<C: Cost = DefaultCost>(Rc<DocInner<C>>);

#[derive(Debug)]
struct DocInner<C: Cost> {
    kind: DocKind<C>,
    id: DocId,
    memo_weight: i8,
    newline_count: usize,
}

#[derive(Debug)]
enum DocKind<C: Cost> {
    Newline(Option<String>),
    Fail,
    Text(String, usize),
    Concat(Doc<C>, Doc<C>),
    Alt(Doc<C>, Doc<C>),
    Align(Doc<C>),
    Reset(Doc<C>),
    Nest(usize, Doc<C>),
    Full(Doc<C>),
    Cost(C, Doc<C>),
}

macro_rules! def_newline {
    ($name:ident, $val:literal) => {
        #[doc = concat!("Creates a newline document that flattens to `", stringify!($val), "`.")]
        pub fn $name<C: Cost>() -> Doc<C> {
            newline(Some($val))
        }
    };
}

macro_rules! def_text {
    ($name:ident, $val:literal) => {
        #[doc = concat!("Creates a document that renders the text `", stringify!($val), "`.")]
        pub fn $name<C: Cost>() -> Doc<C> {
            text($val)
        }
    };
}

def_newline!(nl, " ");
def_newline!(brk, "");

def_text!(comma, ",");
def_text!(lbrack, "[");
def_text!(rbrack, "]");
def_text!(lbrace, "{");
def_text!(rbrace, "}");
def_text!(lparen, "(");
def_text!(rparen, ")");
def_text!(dquote, "\"");
def_text!(space, " ");

/// A newline that cannot be flattened.
///
/// Equivalent to `newline(None)`.
///
/// # Example
///
/// ```
/// # use pretty_expressive::*;
/// let doc = hard_nl();
/// assert_eq!(doc.to_string(), "\n");
///
/// let doc = flatten(hard_nl());
/// assert!(matches!(doc.validate(80), Err(pretty_expressive::Error)));
///
/// let doc = flatten(hard_nl() | text("something else"));
/// assert_eq!(doc.to_string(), "something else");
/// ```
pub fn hard_nl<C: Cost>() -> Doc<C> {
    newline::<C, String>(None)
}

/// Creates a newline document.
///
/// The document renders to a newline character (`'\n'`) followed by the current
/// level of indentation spaces.
///
/// When [`flatten`]ed, if `s` is `Some`, it renders to the string it contains.
/// If `s` is `None`, then when flattened the document will fail to render.
///
/// # Example
///
/// ```
/// # use pretty_expressive::*;
/// let doc = text("[") &
///           newline(Some("")) &
///           text("a") &
///           newline(Some(", ")) &
///           text("b") &
///           newline(Some("")) &
///           text("]");
/// assert_eq!(doc.to_string(),
/// r"[
/// a
/// b
/// ]");
///
/// let doc = flatten(doc);
/// assert_eq!(doc.to_string(), "[a, b]");
/// ```
///
/// # Convenience aliases
///
/// This crate defines some functions for common uses of newlines:
///
/// * [`nl`]: Flattens to `" "` (a single space).
/// * [`brk`]: Flattens to `""` (empty text).
/// * [`hard_nl`]: Fails to flatten.
pub fn newline<C: Cost, S: ToString>(s: Option<S>) -> Doc<C> {
    Doc(Rc::new(DocInner {
        kind: DocKind::Newline(s.map(|s| s.to_string())),
        id: new_id(),
        memo_weight: MEMO_LIMIT - 1,
        newline_count: 1,
    }))
}

/// Creates a document that fails to render.
///
/// This is most useful when used with [choices](Doc::bitor) by making one path
/// fail to render, forcing the printer to choose an alternative.
///
/// # Example
///
/// ```
/// # use pretty_expressive::*;
/// let doc = fail();
/// assert!(matches!(doc.validate(80), Err(pretty_expressive::Error)));
///
/// let doc = fail() | text("not a fail");
/// assert_eq!(doc.to_string(), "not a fail");
/// ```
pub fn fail<C: Cost>() -> Doc<C> {
    Doc(Rc::new(DocInner {
        kind: DocKind::Fail,
        id: new_id(),
        memo_weight: MEMO_LIMIT - 1,
        newline_count: 0,
    }))
}

/// Creates a document that renders a single-line string.
///
/// It is very important that the string not contain any newline characters
/// (`'\n'`), as the printer expects that newlines only come from [`newline`]
/// documents. A `text` with newlines in it will cause the printer to have an
/// incorrect perception of the layouts it is choosing between.
///
/// # Example
///
/// ```
/// # use pretty_expressive::*;
/// let doc = text("Bulbasaur");
/// assert_eq!(doc.to_string(), "Bulbasaur");
/// ```
///
/// # Convenience aliases
///
/// This crate defines some functions for common bits of text:
///
/// * [`comma`][]: `","`
/// * [`lbrack`][]: `"["`
/// * [`rbrack`][]: `"]"`
/// * [`lbrace`][]: `"{"`
/// * [`rbrace`][]: `"}"`
/// * [`lparen`][]: `"("`
/// * [`rparen`][]: `")"`
/// * [`dquote`][]: `"\""`
/// * [`space`][]: `" "`
pub fn text<C: Cost>(s: impl ToString) -> Doc<C> {
    let s = s.to_string();
    let len = s.chars().count();

    Doc(Rc::new(DocInner {
        kind: DocKind::Text(s, len),
        id: new_id(),
        memo_weight: MEMO_LIMIT - 1,
        newline_count: 0,
    }))
}

/// Increase the indentation level while rendering a document.
///
/// Indentation is only affected after the next [`newline`] that is rendered.
/// Content on the current line will not be indented.
///
/// # Example
///
/// ```
/// # use pretty_expressive::*;
/// let doc = text("Bulbasaur") &
///     nest(4, text("Charmander") & nl() & text("Squirtle"));
/// assert_eq!(r"BulbasaurCharmander
///     Squirtle", doc.to_string());
/// ```
pub fn nest<C: Cost>(n: usize, d: Doc<C>) -> Doc<C> {
    use DocKind::*;

    match &d.0.kind {
        Fail | Align(_) | Reset(_) | Text(_, _) => d,
        Cost(c, d) => cost(c.clone(), nest(n, d.clone())),
        _ => {
            let memo_weight = d.weight();
            let newline_count = d.0.newline_count;

            Doc(Rc::new(DocInner {
                kind: DocKind::Nest(n, d),
                id: new_id(),
                memo_weight,
                newline_count,
            }))
        }
    }
}

/// Aligns a document.
///
/// Aligning resets the indentation level while rendering `d` to the starting
/// column of `d`. Any [`newline`]s within `d` will line up with that column.
/// Any uses of [`nest`] within `d` will increase the indentation starting from
/// that column.
///
/// After rendering `d`, the indentation level will return to its previous
/// value.
///
/// Alignment is particularly useful for formatting Lisp code, as Lisps tend to
/// prefer to align children based on the start of their parent, rather than
/// relative to an overall indentation level.
///
/// # Example
///
/// ```
/// # use pretty_expressive::*;
/// let doc = nl() &
///           lparen() &
///           text("+") &
///           space() &
///           align(text("123") &
///                 nl() &
///                 align(text("(let ((a 454))") &
///                       nest(2, nl() &
///                               text("(+ a 2)))"))));
///
/// assert_eq!(doc.to_string(), r"
/// (+ 123
///    (let ((a 454))
///      (+ a 2)))");
/// ```
///
/// This example uses two alignment points. The first wraps the arguments to
/// `+` so that they line up in a column. The second sets the alignment for
/// the `let` form, so that the `nest` inside it will indent subsequent lines
/// two spaces from the start of the `let`. That's not strictly needed in this
/// specific case, since the outer `align` was at the same column, but the inner
/// `align` ensures that wherever the `let` may appear in the document, it will
/// be indented correctly.
pub fn align<C: Cost>(d: Doc<C>) -> Doc<C> {
    use DocKind::*;

    match &d.0.kind {
        Fail | Align(_) | Reset(_) | Text(_, _) => d,
        Cost(c, d) => cost(c.clone(), align(d.clone())),
        _ => {
            let memo_weight = d.weight();
            let newline_count = d.0.newline_count;

            Doc(Rc::new(DocInner {
                kind: DocKind::Align(d),
                id: new_id(),
                memo_weight,
                newline_count,
            }))
        }
    }
}

/// Resets the indentation level for a document to 0.
///
/// This can be useful for things like multiline strings, where the indentation
/// is temporarily reset.
///
/// After rendering `d`, the indentation level will return to its previous
/// value.
///
/// # Example
///
/// ```
/// # use pretty_expressive::*;
/// let doc = text("def gen1_starters():") &
///           nest(4, nl() &
///                   text("print ") &
///                   reset(text("'''") & nl() &
///                         text("Bulbasaur") & nl() &
///                         text("Charmander") & nl() &
///                         text("Squirtle") & nl() &
///                         text("'''")) &
///                   nl() &
///                   text("return True"));
///
/// assert_eq!(doc.to_string(),
/// r"def gen1_starters():
///     print '''
/// Bulbasaur
/// Charmander
/// Squirtle
/// '''
///     return True");
/// ```
pub fn reset<C: Cost>(d: Doc<C>) -> Doc<C> {
    use DocKind::*;

    match &d.0.kind {
        Fail | Align(_) | Reset(_) | Text(_, _) => d,
        Cost(c, d) => cost(c.clone(), reset(d.clone())),
        _ => {
            let memo_weight = d.weight();
            let newline_count = d.0.newline_count;

            Doc(Rc::new(DocInner {
                kind: DocKind::Reset(d),
                id: new_id(),
                memo_weight,
                newline_count,
            }))
        }
    }
}

/// Requires that a document not be followed by any more text on the same line.
///
/// If more text is placed after this document without moving to a new line,
/// the document will fail to render. Note that this doesn't introduce the new
/// line on its own. Instead, it forces the printer to choose paths that will
/// uphold the constraint.
///
/// A typical use-case for this is line comments, where additional code cannot
/// be placed after the comment without becoming part of the comment text. By
/// wrapping the comment text in `full`, you ensure that the printer will not
/// produce a layout that changes the meaning of the document by placing code
/// tokens on the comment line.
///
/// # Example
///
/// ```
/// # use pretty_expressive::*;
/// let comment = full(text(";; this comment can't have code after it"));
/// let code = text("(print 123)");
///
/// let doc = comment.clone() & nl() & code.clone();
/// assert_eq!(doc.to_string(),
/// r";; this comment can't have code after it
/// (print 123)");
///
/// let doc = comment.clone() & code.clone();
/// assert!(matches!(doc.validate(80), Err(pretty_expressive::Error)));
///
/// // text afterwards is allowed if it is zero-length
/// let doc = comment.clone() & text("");
/// assert_eq!(
///     doc.to_string(),
///     ";; this comment can't have code after it"
/// );
/// ```
pub fn full<C: Cost>(d: Doc<C>) -> Doc<C> {
    use DocKind::*;

    match &d.0.kind {
        Full(_) => d,
        Fail => fail(),
        _ => {
            let memo_weight = d.weight();
            let newline_count = d.0.newline_count;

            Doc(Rc::new(DocInner {
                kind: DocKind::Full(d),
                id: new_id(),
                memo_weight,
                newline_count,
            }))
        }
    }
}

/// Introduces an extra cost to a document.
///
/// This can be used to steer the printer away from making certain choices while
/// still including them as an option. The cost `c` will be added to whatever
/// cost would normally be assigned to the document.
///
/// # Example
///
/// Normally, when everything fits in the page width, the printer will prefer
/// to print things flatter, since it adds a cost for each newline added to
/// the layout.
///
/// ```
/// # use pretty_expressive::*;
/// let doc = text("hello world") | (text("hello") & hard_nl() & text("world"));
/// assert_eq!(doc.to_string(), "hello world");
/// ```
///
/// We can make the flatter option have a greater cost, which will cause the
/// printer to choose the taller layout instead.
///
/// ```
/// # use pretty_expressive::*;
/// let doc = cost(DefaultCost(0, 2), text("hello world")) |
///           (text("hello") & hard_nl() & text("world"));
///
/// assert_eq!(doc.to_string(),
/// r"hello
/// world");
/// ```
pub fn cost<C: Cost>(c: C, d: Doc<C>) -> Doc<C> {
    if matches!(&d.0.kind, DocKind::Fail) {
        d
    } else {
        let memo_weight = d.weight();
        let newline_count = d.0.newline_count;

        Doc(Rc::new(DocInner {
            kind: DocKind::Cost(c, d),
            id: new_id(),
            memo_weight,
            newline_count,
        }))
    }
}

/// The `&` operator is used to concatenate documents.
///
/// This is the fundamental operator for creating a larger document out of
/// smaller ones.
impl<C: Cost> BitAnd<Doc<C>> for Doc<C> {
    /// Concatenation forms a new document.
    type Output = Doc<C>;

    /// Concatenates two documents.
    ///
    /// This places the documents one after the other in the layout. No
    /// additional spacing or alignment is added.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = text("hello") & space() & text("world");
    /// assert_eq!(doc.to_string(), "hello world");
    /// ```
    fn bitand(self, rhs: Doc<C>) -> Self::Output {
        use DocKind::*;

        match (&self.0.kind, &rhs.0.kind) {
            (Fail, _) | (_, Fail) => fail(),
            (Text(_, 0), _) => rhs,
            (_, Text(_, 0)) => self,
            (Full(_), Text(_, _)) => fail(),
            (Text(s1, l1), Text(s2, l2)) => {
                let mut s = s1.clone();
                s.push_str(s2.as_str());
                Doc(Rc::new(DocInner {
                    kind: DocKind::Text(s, l1 + l2),
                    id: new_id(),
                    memo_weight: MEMO_LIMIT - 1,
                    newline_count: 0,
                }))
            }
            (_, Cost(c, d2)) => cost(c.clone(), self & d2.clone()),
            (Cost(c, d1), _) => cost(c.clone(), d1.clone() & rhs),
            _ => {
                let left_nl_count = self.0.newline_count;
                let right_nl_count = rhs.0.newline_count;
                let memo_weight = self.weight().min(rhs.weight());

                Doc(Rc::new(DocInner {
                    kind: DocKind::Concat(self, rhs),
                    id: new_id(),
                    memo_weight,
                    newline_count: left_nl_count + right_nl_count,
                }))
            }
        }
    }
}

/// The `|` operator is used to create a choice between multiple documents.
///
/// This is the fundamental operator for giving the printer options for
/// different ways to layout a document.
impl<C: Cost> BitOr<Doc<C>> for Doc<C> {
    /// A choice between two documents is a new document.
    type Output = Doc<C>;

    /// Creates a document that will be rendered to one of two documents.
    ///
    /// The printer will determine which side of the choice is prettier and will
    /// render using that layout.
    ///
    /// A choice should generally include the same content, but with different
    /// formatting. That said, there is no restriction on what appears on either
    /// side of a choice: they can be completely different if that is what
    /// serves your needs.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = text("hello world") |
    ///           (text("hello") & hard_nl() & text("world"));
    /// assert_eq!(doc.to_string(), "hello world");
    /// ```
    ///
    /// # Sharing subdocuments
    ///
    /// The printer is able to take advantage of the fact that the tree of
    /// choices for a document isn't actually a tree: it's a DAG (directed
    /// acyclic graph). Because much of the content on either side of the
    /// choice is the same, the printer can reuse calculations if it knows which
    /// subdocuments are equivalent. Finding the optimal layout for the same
    /// document at the same column and indentation level will always give the
    /// same result, but the printer might reach that through many different
    /// paths through the choice graph.
    ///
    /// To cache computed results, each [`Doc`] is assigned an ID internally.
    /// `Doc`s are reference-counted (using [`Rc`]) internally, so when you
    /// `clone()` a `Doc`, you get another reference to the same document, with
    /// the same ID. For this reason, cloning documents to reuse on different
    /// sides of a choice is ideal. So this:
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let hello = text("hello");
    /// let world = text("world");
    ///
    /// let doc = v_append(hello.clone(), world.clone()) |
    ///           us_append(hello.clone(), world.clone());
    /// # assert_eq!(doc.to_string(), "hello world");
    /// ```
    ///
    /// is always preferable to this:
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = v_append(text("hello"), text("world")) |
    ///           us_append(text("hello"), text("world"));
    /// # assert_eq!(doc.to_string(), "hello world");
    /// ```
    ///
    /// Even if they will produce the same result. It may not make a big
    /// difference in this small of an example, but in practice, there can be
    /// many subdocuments behind each side of a choice, and each subsequent
    /// choice compounds that exponentially.
    fn bitor(self, rhs: Doc<C>) -> Self::Output {
        use DocKind::Fail;

        match (&self.0.kind, &rhs.0.kind) {
            (Fail, _) => rhs,
            (_, Fail) => self,
            _ => {
                let left_nl_count = self.0.newline_count;
                let right_nl_count = rhs.0.newline_count;
                let memo_weight = self.weight().min(rhs.weight());

                Doc(Rc::new(DocInner {
                    kind: DocKind::Alt(self, rhs),
                    id: new_id(),
                    memo_weight,
                    newline_count: left_nl_count.max(right_nl_count),
                }))
            }
        }
    }
}

impl<C: Cost> Clone for Doc<C> {
    /// Creates a new reference to the same document.
    ///
    /// `Doc`s are internally reference-counted.
    fn clone(&self) -> Self {
        Doc(Rc::clone(&self.0))
    }
}

macro_rules! def_append_concat {
    (
        $( #[$append_meta:meta] )*
        fn $append_name:ident ( $x:ident , $y:ident ) $block:block

        $( #[$concat_meta:meta] )*
        fn $concat_name:ident;
    ) => {
        $( #[$append_meta] )*
        pub fn $append_name<C: Cost>($x: Doc<C>, $y: Doc<C>) -> Doc<C> $block

        $( #[$concat_meta] )*
        pub fn $concat_name<C: Cost>(xs: impl IntoIterator<Item = Doc<C>>) -> Doc<C> {
            let mut iter = xs.into_iter();
            if let Some(next) = iter.next() {
                iter.fold(next, $append_name)
            } else {
                text("")
            }
        }
    }
}

def_append_concat! {
    /// Concatenates two documents horizontally.
    ///
    /// To combine an iterator of documents, use [`concat()`].
    ///
    /// Equivalent to `x & y`. See [`Doc::bitand`] for more details.
    fn u_append(x, y) { x & y }

    /// Concatenates several documents into one.
    ///
    /// Equivalent to calling [`&`](Doc::bitand)/[`u_append`] successively to
    /// combine the documents in the iterator. If the iterator is empty, it
    /// returns `text("")`.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = concat([text("hello"), space(), text("world")]);
    /// assert_eq!(doc.to_string(), "hello world");
    ///
    /// let doc = concat([]);
    /// assert_eq!(doc.to_string(), "");
    /// ```
    fn concat;
}

def_append_concat! {
    /// Concatenates two documents vertically.
    ///
    /// The documents will be separated by an unflattenable newline. To combine
    /// more than two documents or an iterator of documents, use [`v_concat`].
    ///
    /// Equivalent to `x & hard_nl() & y`.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = v_append(text("hello"), text("world"));
    /// assert_eq!(doc.to_string(), "hello\nworld");
    /// ```
    fn v_append(x, y) { x & hard_nl() & y }

    /// Concatenates several documents vertically.
    ///
    /// Equivalent to calling [`v_append`] successively to combine the documents
    /// in the iterator. If the iterator is empty, it returns `text("")`.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = v_concat([text("hello"), text("my"), text("friend")]);
    /// assert_eq!(doc.to_string(),
    /// r"hello
    /// my
    /// friend");
    ///
    /// let doc = v_concat([]);
    /// assert_eq!(doc.to_string(), "");
    /// ```
    fn v_concat;
}

def_append_concat! {
    /// Concatenates two documents horizontally with alignment.
    ///
    /// If `y` contains newlines, those lines will stay aligned with
    /// the start of `y`, rather than flowing back to the current indentation
    /// level.
    ///
    /// To combine more than two documents or an iterator of documents, use
    /// [`a_concat`].
    ///
    /// Equivalent to `x & align(y)`.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = a_append(nl() & text("hello "),
    ///                    text("my") & nl() & text("friend"));
    /// assert_eq!(doc.to_string(), r"
    /// hello my
    ///       friend");
    /// ```
    fn a_append(x, y) { x & align(y) }

    /// Concatenates several documents horizontally with alignment.
    ///
    /// Equivalent to calling [`a_append`] successively to combine the documents
    /// in the iterator. If the iterator is empty, it returns `text("")`.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = a_concat([
    ///     nl() & text("hello "),
    ///     text("my") & nl() & text("friend "),
    ///     text("how are") & nl() & text("you?"),
    /// ]);
    /// assert_eq!(doc.to_string(), r"
    /// hello my
    ///       friend how are
    ///              you?");
    ///
    /// let doc = a_concat([]);
    /// assert_eq!(doc.to_string(), "");
    /// ```
    fn a_concat;
}

def_append_concat! {
    /// Concatenates two documents horizontally with spacing and alignment.
    ///
    /// Similar to [`a_append`], but with a space included between the documents.
    ///
    /// To combine more than two documents or an iterator of documents, use
    /// [`as_concat`].
    ///
    /// Equivalent to `x & space() & align(y)`.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = as_append(nl() & text("hello"),
    ///                     text("my") & nl() & text("friend"));
    /// assert_eq!(doc.to_string(), r"
    /// hello my
    ///       friend");
    /// ```
    fn as_append(x, y) { x & space() & align(y) }

    /// Concatenates several documents horizontally with spacing and alignment.
    ///
    /// Equivalent to calling [`as_append`] successively to combine the documents
    /// in the iterator. If the iterator is empty, it returns `text("")`.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = as_concat([
    ///     nl() & text("hello"),
    ///     text("my") & nl() & text("friend"),
    ///     text("how are") & nl() & text("you?"),
    /// ]);
    /// assert_eq!(doc.to_string(), r"
    /// hello my
    ///       friend how are
    ///              you?");
    ///
    /// let doc = a_concat([]);
    /// assert_eq!(doc.to_string(), "");
    /// ```
    fn as_concat;
}

def_append_concat! {
    /// Concatenates two documents horizontally with spacing.
    ///
    /// To combine more than two documents or an iterator of documents, use
    /// [`us_concat`].
    ///
    /// Equivalent to `x & space() & y`.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = us_append(text("hello"), text("world"));
    /// assert_eq!(doc.to_string(), "hello world");
    /// ```
    fn us_append(x, y) { x & space() & y }

    /// Concatenates several documents horizontally with spacing.
    ///
    /// Equivalent to calling [`us_append`] successively to combine the documents
    /// in the iterator. If the iterator is empty, it returns `text("")`.
    ///
    /// # Example
    ///
    /// ```
    /// # use pretty_expressive::*;
    /// let doc = us_concat([text("hello"), text("world")]);
    /// assert_eq!(doc.to_string(), "hello world");
    ///
    /// let doc = us_concat([]);
    /// assert_eq!(doc.to_string(), "");
    /// ```
    fn us_concat;
}

/// Create a flattened version of a document.
///
/// Flattening converts all newlines within a document to the flat alternative
/// that was provided to [`newline`], producing a document that can be rendered
/// on a single line. If any newlines within the document provided `None` for
/// their alternative (e.g. [`hard_nl`]), then the flattened document will fail
/// to render, forcing the printer to choose another path.
///
/// # Example
///
/// ```
/// # use pretty_expressive::*;
/// let doc = text("a") & nl() & text("b") & nl() & text("c");
/// assert_eq!(doc.to_string(), r"a
/// b
/// c");
///
/// let doc = flatten(doc);
/// assert_eq!(doc.to_string(), "a b c");
///
/// let doc = text("a") & brk() & text("b") & brk() & text("c");
/// assert_eq!(doc.to_string(), r"a
/// b
/// c");
///
/// let doc = flatten(doc);
/// assert_eq!(doc.to_string(), "abc");
///
/// let doc = text("a") & hard_nl() & text("b") & hard_nl() & text("c");
/// assert_eq!(doc.to_string(), r"a
/// b
/// c");
///
/// let doc = flatten(doc);
/// assert!(matches!(doc.validate(80), Err(pretty_expressive::Error)));
/// ```
pub fn flatten<C: Cost>(x: Doc<C>) -> Doc<C> {
    use DocKind::*;

    let mut cache: HashMap<DocId, Doc<C>> = HashMap::new();

    fn flatten_inner<C: crate::cost::Cost>(
        cache: &mut HashMap<DocId, Doc<C>>,
        x: Doc<C>,
    ) -> Doc<C> {
        if let Some(cached) = cache.get(&x.0.id) {
            cached.clone()
        } else {
            let id = x.0.id;
            let result = {
                match &x.0.kind {
                    Fail | Text(_, _) => x,
                    Newline(None) => fail(),
                    Newline(Some(s)) => text(s),
                    Concat(a, b) => {
                        let ap = flatten_inner(cache, a.clone());
                        let bp = flatten_inner(cache, b.clone());
                        if ap.0.id == a.0.id && bp.0.id == b.0.id {
                            x
                        } else {
                            ap & bp
                        }
                    }
                    Alt(a, b) => {
                        let ap = flatten_inner(cache, a.clone());
                        let bp = flatten_inner(cache, b.clone());
                        if ap.0.id == a.0.id && bp.0.id == b.0.id {
                            x
                        } else {
                            ap | bp
                        }
                    }
                    Nest(_, d) | Align(d) | Reset(d) | Full(d) => flatten_inner(cache, d.clone()),
                    Cost(c, d) => {
                        let dp = flatten(d.clone());
                        if dp.0.id == d.0.id {
                            x
                        } else {
                            cost(c.clone(), dp)
                        }
                    }
                }
            };
            cache.insert(id, result.clone());
            result
        }
    }

    flatten_inner(&mut cache, x)
}

/// Create a choice between a document and its [`flatten`]ed version.
///
/// # Example
///
/// ```
/// # use pretty_expressive::*;
/// let doc = text("hello") & nl() & text("world");
/// assert_eq!(format!("{doc}"), "hello\nworld");
///
/// let doc = group(doc);
/// assert_eq!(format!("{doc}"), "hello world");
/// assert_eq!(format!("{doc:10}"), "hello\nworld");
/// ```
pub fn group<C: Cost>(x: Doc<C>) -> Doc<C> {
    x.clone() | flatten(x)
}

impl<C: Cost> DocKind<C> {
    pub(crate) fn fails(&self, full_before: bool, full_after: bool) -> bool {
        use DocKind::*;

        match (self, full_before, full_after) {
            (Fail, _, _) => true,
            (Newline(_), _, full_after) => full_after,
            (Text(_, _), false, false) => false,
            (Text(_, _), true, false) | (Text(_, _), false, true) => true,
            (Text(_, l), true, true) => *l > 0,
            (Full(_), _, full_after) => !full_after,
            _ => false,
        }
    }
}

fn new_id() -> DocId {
    GLOBAL_ID.with(|id| {
        let new_id = id.get();
        id.set(new_id + 1);
        DocId(new_id)
    })
}

impl<C: Cost> Doc<C> {
    fn weight(&self) -> i8 {
        if self.0.memo_weight == 0 {
            MEMO_LIMIT - 1
        } else {
            self.0.memo_weight - 1
        }
    }
}