blob: a9805b366bed7dcbb0088c39e7c47e27c2d26f0b [file]
/-
Copyright (c) 2018 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Author: Leonardo de Moura
-/
module
prelude
public import Init.Data.Int.Basic
public import Init.Data.String.Bootstrap
import Init.Control.State
import Init.Data.Nat.Bitwise.Basic
public section
namespace Std
/--
Determines how groups should have linebreaks inserted when the text would overfill its remaining
space.
- `allOrNone` will make a linebreak on every `Format.line` in the group or none of them.
```
[1,
2,
3]
```
- `fill` will only make linebreaks on as few `Format.line`s as possible:
```
[1, 2,
3]
```
-/
inductive Format.FlattenBehavior where
/--
Either all `Format.line`s in the group will be newlines, or all of them will be spaces.
-/
| allOrNone
/--
As few `Format.line`s in the group as possible will be newlines.
-/
| fill
deriving Inhabited, BEq
open Format in
/--
A representation of a set of strings, in which the placement of newlines and indentation differ.
Given a specific line width, specified in columns, the string that uses the fewest lines can be
selected.
The pretty-printing algorithm is based on Wadler's paper
[_A Prettier Printer_](https://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf).
-/
inductive Format where
/-- The empty format. -/
| nil : Format
/--
A position where a newline may be inserted if the current group does not fit within the allotted
column width.
-/
| line : Format
/--
`align` tells the formatter to pad with spaces to the current indentation level, or else add a
newline if we are already at or past the indent.
If `force` is true, then it will pad to the indent even if it is in a flattened group.
Example:
```lean example
open Std Format in
#eval IO.println (nest 2 <| "." ++ align ++ "a" ++ line ++ "b")
```
```lean output
. a
b
```
-/
| align (force : Bool) : Format
/--
A node containing a plain string.
If the string contains newlines, the formatter emits them and then indents to the current level.
-/
| text : String → Format
/--
`nest indent f` increases the current indentation level by `indent` while rendering `f`.
Example:
```lean example
open Std Format in
def fmtList (l : List Format) : Format :=
let f := joinSep l (", " ++ Format.line)
group (nest 1 <| "[" ++ f ++ "]")
```
This will be written all on one line, but if the text is too large, the formatter will put in
linebreaks after the commas and indent later lines by 1.
-/
| nest (indent : Int) (f : Format) : Format
/-- Concatenation of two `Format`s. -/
| append : Format → Format → Format
/-- Creates a new flattening group for the given inner `Format`. -/
| group : Format → (behavior : FlattenBehavior := FlattenBehavior.allOrNone) → Format
/-- Used for associating auxiliary information (e.g. `Expr`s) with `Format` objects. -/
| tag : Nat → Format → Format
deriving Inhabited
namespace Format
/-- Checks whether the given format contains no characters. -/
def isEmpty : Format → Bool
| nil => true
| line => false
| align _ => true
| text msg => msg == ""
| nest _ f => f.isEmpty
| append f₁ f₂ => f₁.isEmpty && f₂.isEmpty
| group f _ => f.isEmpty
| tag _ f => f.isEmpty
/--
Creates a group in which as few `Format.line`s as possible are rendered as newlines.
This is an alias for `Format.group`, with `FlattenBehavior` set to `fill`.
-/
def fill (f : Format) : Format :=
group f (behavior := FlattenBehavior.fill)
instance : Append Format := ⟨Format.append⟩
instance : Coe String Format := ⟨text⟩
/--
Concatenates a list of `Format`s with `++`.
-/
def join (xs : List Format) : Format :=
xs.foldl (·++·) ""
/--
Checks whether a `Format` is the constructor `Format.nil`.
This does not check whether the resulting rendered strings are always empty. To do that, use
`Format.isEmpty`.
-/
def isNil : Format → Bool
| nil => true
| _ => false
private structure SpaceResult where
foundLine : Bool := false
foundFlattenedHardLine : Bool := false
space : Nat := 0
deriving Inhabited
@[inline] private def merge (w : Nat) (r₁ : SpaceResult) (r₂ : Nat → SpaceResult) : SpaceResult :=
if r₁.space > w || r₁.foundLine then
r₁
else
let r₂ := r₂ (w - r₁.space);
{ r₂ with space := r₁.space + r₂.space }
private def spaceUptoLine : Format → Bool → Int → Nat → SpaceResult
| nil, _, _, _ => {}
| line, flatten, _, _ => if flatten then { space := 1 } else { foundLine := true }
| align force, flatten, m, w =>
if flatten && !force then {}
else if w < m then
{ space := (m - w).toNat }
else
{ foundLine := true }
| text s, flatten, _, _ =>
let p := String.Internal.posOf s '\n'
let off := String.Internal.offsetOfPos s p
{ foundLine := p != s.rawEndPos, foundFlattenedHardLine := flatten && p != s.rawEndPos, space := off }
| append f₁ f₂, flatten, m, w => merge w (spaceUptoLine f₁ flatten m w) (spaceUptoLine f₂ flatten m)
| nest n f, flatten, m, w => spaceUptoLine f flatten (m - n) w
| group f _, _, m, w => spaceUptoLine f true m w
| tag _ f, flatten, m, w => spaceUptoLine f flatten m w
private structure WorkItem where
f : Format
indent : Int
activeTags : Nat
/--
A directive indicating whether a given work group is able to be flattened.
- `allow` indicates that the group is allowed to be flattened; its argument is `true` if
there is sufficient space for it to be flattened (and so it should be), or `false` if not.
- `disallow` means that this group should not be flattened irrespective of space concerns.
This is used at levels of a `Format` outside of any flattening groups. It is necessary to track
this so that, after a hard line break, we know whether to try to flatten the next line.
-/
inductive FlattenAllowability where
| allow (fits : Bool)
| disallow
deriving BEq
/-- Whether the given directive indicates that flattening should occur. -/
def FlattenAllowability.shouldFlatten : FlattenAllowability → Bool
| allow true => true
| _ => false
private structure WorkGroup where
fla : FlattenAllowability
flb : FlattenBehavior
items : List WorkItem
private partial def spaceUptoLine' : List WorkGroup → Nat → Nat → SpaceResult
| [], _, _ => {}
| { items := [], .. }::gs, col, w => spaceUptoLine' gs col w
| g@{ items := i::is, .. }::gs, col, w =>
merge w
(spaceUptoLine i.f g.fla.shouldFlatten (w + col - i.indent) w)
(spaceUptoLine' ({ g with items := is }::gs) col)
/--
A monad that can be used to incrementally render `Format` objects.
-/
class MonadPrettyFormat (m : Type → Type) where
/--
Emits the string `s`.
-/
pushOutput (s : String) : m Unit
/--
Emits a newline followed by `indent` columns of indentation.
-/
pushNewline (indent : Nat) : m Unit
/--
Gets the current column at which the next string will be emitted.
-/
currColumn : m Nat
/--
Starts a region tagged with `tag`.
-/
startTag (tag : Nat) : m Unit
/--
Exits the scope of `count` opened tags.
-/
endTags (count : Nat) : m Unit
open MonadPrettyFormat
private def pushGroup (flb : FlattenBehavior) (items : List WorkItem) (gs : List WorkGroup) (w : Nat) [Monad m] [MonadPrettyFormat m] : m (List WorkGroup) := do
let k ← currColumn
-- Flatten group if it + the remainder (gs) fits in the remaining space. For `fill`, measure only up to the next (ungrouped) line break.
let g := { fla := .allow (flb == FlattenBehavior.allOrNone), flb := flb, items := items : WorkGroup }
let r := spaceUptoLine' [g] k (w-k)
let r' := merge (w-k) r (spaceUptoLine' gs k)
-- Prevent flattening if any item contains a hard line break, except within `fill` if it is ungrouped (=> unflattened)
return { g with fla := .allow (!r.foundFlattenedHardLine && r'.space <= w-k) }::gs
private partial def be (w : Nat) [Monad m] [MonadPrettyFormat m] : List WorkGroup → m Unit
| [] => pure ()
| { items := [], .. }::gs => be w gs
| g@{ items := i::is, .. }::gs => do
let gs' (is' : List WorkItem) := { g with items := is' }::gs;
match i.f with
| nil =>
endTags i.activeTags
be w (gs' is)
| tag t f =>
startTag t
be w (gs' ({ i with f, activeTags := i.activeTags + 1 }::is))
| append f₁ f₂ => be w (gs' ({ i with f := f₁, activeTags := 0 }::{ i with f := f₂ }::is))
| nest n f => be w (gs' ({ i with f, indent := i.indent + n }::is))
| text s =>
let p := String.Internal.posOf s '\n'
if p == s.rawEndPos then
pushOutput s
endTags i.activeTags
be w (gs' is)
else
pushOutput (String.Internal.extract s {} p)
pushNewline i.indent.toNat
let is := { i with f := text (String.Internal.extract s (String.Internal.next s p) s.rawEndPos) }::is
-- after a hard line break, re-evaluate whether to flatten the remaining group
-- note that we shouldn't start flattening after a hard break outside a group
if g.fla == .disallow then
be w (gs' is)
else
pushGroup g.flb is gs w >>= be w
| line =>
match g.flb with
| FlattenBehavior.allOrNone =>
if g.fla.shouldFlatten then
-- flatten line = text " "
pushOutput " "
endTags i.activeTags
be w (gs' is)
else
pushNewline i.indent.toNat
endTags i.activeTags
be w (gs' is)
| FlattenBehavior.fill =>
let breakHere := do
pushNewline i.indent.toNat
-- make new `fill` group and recurse
endTags i.activeTags
pushGroup FlattenBehavior.fill is gs w >>= be w
-- if preceding fill item fit in a single line, try to fit next one too
if g.fla.shouldFlatten then
let gs'@(g'::_) ← pushGroup FlattenBehavior.fill is gs (w - String.Internal.length " ")
| panic "unreachable"
if g'.fla.shouldFlatten then
pushOutput " "
endTags i.activeTags
be w gs' -- TODO: use `return`
else
breakHere
else
breakHere
| align force =>
if g.fla.shouldFlatten && !force then
-- flatten (align false) = nil
endTags i.activeTags
be w (gs' is)
else
let k ← currColumn
if k < i.indent then
pushOutput (String.Internal.pushn "" ' ' (i.indent - k).toNat)
endTags i.activeTags
be w (gs' is)
else
pushNewline i.indent.toNat
endTags i.activeTags
be w (gs' is)
| group f flb =>
if g.fla.shouldFlatten then
-- flatten (group f) = flatten f
be w (gs' ({ i with f }::is))
else
pushGroup flb [{ i with f }] (gs' is) w >>= be w
/- Render the given `f : Format` with a line width of `w`.
`indent` is the starting amount to indent each line by. -/
/--
Renders a `Format` using effects in the monad `m`, using the methods of `MonadPrettyFormat`.
Each line is emitted as soon as it is rendered, rather than waiting for the entire document to be
rendered.
* `w`: the total width
* `indent`: the initial indentation to use for wrapped lines (subsequent wrapping may increase the
indentation)
-/
def prettyM (f : Format) (w : Nat) (indent : Nat := 0) [Monad m] [MonadPrettyFormat m] : m Unit :=
be w [{ flb := FlattenBehavior.allOrNone, fla := .disallow, items := [{ f := f, indent, activeTags := 0 }]}]
/--
Creates a format `l ++ f ++ r` with a flattening group, nesting the contents by the length of `l`.
The group's `FlattenBehavior` is `allOrNone`; for `fill` use `Std.Format.bracketFill`.
-/
@[inline] def bracket (l : String) (f : Format) (r : String) : Format :=
group (nest (String.Internal.length l) $ l ++ f ++ r)
/--
Creates the format `"(" ++ f ++ ")"` with a flattening group, nesting by one space.
-/
@[inline] def paren (f : Format) : Format :=
bracket "(" f ")"
/--
Creates the format `"[" ++ f ++ "]"` with a flattening group, nesting by one space.
`sbracket` is short for “square bracket”.
-/
@[inline] def sbracket (f : Format) : Format :=
bracket "[" f "]"
/--
Creates a format `l ++ f ++ r` with a flattening group, nesting the contents by the length of `l`.
The group's `FlattenBehavior` is `fill`; for `allOrNone` use `Std.Format.bracketFill`.
-/
@[inline] def bracketFill (l : String) (f : Format) (r : String) : Format :=
fill (nest (String.Internal.length l) $ l ++ f ++ r)
/-- The default indentation level, which is two spaces. -/
def defIndent := 2
def defUnicode := true
/-- The default width of the targeted output, which is 120 columns. -/
def defWidth := 120
/--
Increases the indentation level by the default amount.
-/
def nestD (f : Format) : Format :=
nest defIndent f
/-- Insert a newline and then `f`, all nested by the default indent amount. -/
def indentD (f : Format) : Format :=
nestD (Format.line ++ f)
/-- State for formatting a pretty string. -/
private structure State where
out : String := ""
column : Nat := 0
private instance : MonadPrettyFormat (StateM State) where
-- We avoid a structure instance update, and write these functions using pattern matching because of issue #316
pushOutput s := modify fun ⟨out, col⟩ => ⟨String.Internal.append out s, col + (String.Internal.length s)⟩
pushNewline indent := modify fun ⟨out, _⟩ => ⟨String.Internal.append out (String.Internal.pushn "\n" ' ' indent), indent⟩
currColumn := return (← get).column
startTag _ := return ()
endTags _ := return ()
/--
Renders a `Format` to a string.
* `width`: the total width
* `indent`: the initial indentation to use for wrapped lines
(subsequent wrapping may increase the indentation)
* `column`: begin the first line wrap `column` characters earlier than usual
(this is useful when the output String will be printed starting at `column`)
-/
def pretty (f : Format) (width : Nat := defWidth) (indent : Nat := 0) (column := 0) : String :=
let act : StateM State Unit := prettyM f width indent
State.out <| act (State.mk "" column) |>.snd
end Format
/--
Specifies a “user-facing” way to convert from the type `α` to a `Format` object. There is no
expectation that the resulting string is valid code.
The `Repr` class is similar, but the expectation is that instances produce valid Lean code.
-/
class ToFormat (α : Type u) where
/--
Converts a value to a `Format` object, with no expectation that the resulting string is valid
code.
-/
format : α → Format
export ToFormat (format)
-- note: must take precedence over the above instance to avoid premature formatting
instance : ToFormat Format where
format f := f
instance : ToFormat String where
format s := Format.text s
/--
Intercalates the given list with the given `sep` format.
The list items are formatting using `ToFormat.format`.
-/
def Format.joinSep {α : Type u} [ToFormat α] : List α → Format → Format
| [], _ => nil
| [a], _ => format a
| a::as, sep => as.foldl (· ++ sep ++ format ·) (format a)
/--
Concatenates the given list after prepending `pre` to each element.
The list items are formatting using `ToFormat.format`.
-/
def Format.prefixJoin {α : Type u} [ToFormat α] (pre : Format) : List α → Format
| [] => nil
| a::as => as.foldl (· ++ pre ++ format ·) (pre ++ format a)
/--
Concatenates the given list after appending the given suffix to each element.
The list items are formatting using `ToFormat.format`.
-/
def Format.joinSuffix {α : Type u} [ToFormat α] : List α → Format → Format
| [], _ => nil
| a::as, suffix => as.foldl (· ++ format · ++ suffix) (format a ++ suffix)
end Std