如何编写代码格式化程序

2024 年 4 月 13 日

询问十位开发人员，他们认为应该如何格式化某段代码，您可能会得到十种不同的意见。更糟糕的是，这些观点几乎从来没有基于事实。相反，当你问为什么他们更喜欢 X 风格而不是 Y 风格时，答案几乎总是相当于“我就是喜欢”。

如果我们可以回避整个争论并让计算机为我们做出决定会怎么样？不，我不是在谈论要求 ChatGPT 为您格式化代码，我是在谈论“代码格式化程序”。

代码格式化程序是一个程序，它将源代码作为输入，使用特定样式对其进行格式化，然后将其写回磁盘或 STDOUT。虽然此类工具已存在很长时间，但在过去 15 年左右的时间里，它们的使用变得越来越流行。去的
戈夫姆特特别是似乎是更多使用代码格式化程序背后的推动力，因为当今使用的许多流行格式化程序在 gofmt 发布后的几年中开始出现。为了说明这一点，这里列出了似乎相当流行的各种格式化程序，以及它们首次引入的年份：

我怀疑 gofmt 本身并不是一个特别值得注意的格式化程序（除了不允许您以任何方式配置它，因为它应该是），而是 Go 本身非常受欢迎，因此让许多开发人员感受到了它的美丽不必担心手动格式化代码。随着时间的推移，这种情况逐渐流行起来，导致自引入 gofmt 以来可用代码格式化程序的数量不断增加。

那么如何实际构建代码格式化程序呢？是否需要数十年的 Haskell 工作经验并掌握 monad 的方式？或者也许您必须阅读数百篇计算机科学论文才能理解 lambda 的深层含义？为了更好地理解整个计算机科学，在麻省理工学院学习四年，背负沉重的学生债务怎么样？

不，编写一个像样的代码格式化程序实际上很简单，只是没有像计算机科学中的许多其他主题那样以简单的方式进行解释。幸运的是，我最近花了几周的时间编写了一个代码格式化程序
印科，所以我现在自然是与代码格式化相关的所有方面的专家。

我们将在本文中介绍的设置基于 Inko 的格式化程序，而 Inko 的格式化程序又基于更漂亮和纸 “更漂亮的打印机”
（如果我没记错的话，Prettier 也是基于它的）。这篇论文本身有点平凡，我已经忘记了 80%，但概念却很简单。

我们将使用 Inko 作为选择的语言来展示如何编写格式化程序，但将代码翻译成不同的语言应该很容易。

哦，在我忘记之前：如果您也有兴趣了解如何实现模式匹配，请看一下这个 Git 存储库其中包含 Rust 中的两个实现。就像我们今天要讨论的代码一样，Rust 代码有很好的文档记录，并且应该很容易理解。有趣的事实：
微光基于此确切代码的模式匹配实现。整洁的！

节点和树

格式化程序的基本思想如下：我们采用某种抽象语法树（AST），特别是包含注释的树，并将其转换为格式化树。格式化树具有各种节点，例如“仅渲染此文本”或“尝试将所有子节点放在一行上”。构建树后，我们访问每个节点并将其呈现为字符串。然后将生成的字符串写入文件或 STDOUT。

我们的树将使用总和类型或“枚举”创建。在 Inko 中，您可以按如下方式定义枚举：

class enum Letter {
  case A
  case B
  case C
}

Rust 的等价物如下：

在 Inko 中，枚举案例可以在定义时包装值，如下所示：

class enum Option[T] {
  # This case stores some value of type "T", whatever that is.
  case Some(T)
  case None
}

在 Inko 中，您可以像这样创建一个枚举实例：

Option.Some(42)
Option.None

对于我们的树，我们将从基本定义开始：

现在让我们看看我们需要的不同节点。

文本

我们树的两个最基本的节点是 Text(value) 和 Unicode(value, size)。

这 Text 节点存储一个 ASCII 字符串（例如您语言中的关键字），而 Unicode 节点存储包含一个或多个多字节字符的字符串，及其表示为扩展字素簇数量的大小。尺寸为 Unicode 节点被缓存，因为根据树的结构，我们最终可能必须多次计算此类节点的宽度。由于计算字素簇是一个 O(n) 操作时，缓存该值会加快速度。

我们将这些节点定义如下：

class enum Node {
  case Text(String)
  case Unicode(String, Int)
}

这 String 参数存储要渲染的字符串，而 Int 参数用于存储扩展字素簇的数量。为了 Unicode 我们还将添加一个辅助方法来使构建它们更容易一些：

class enum Node {
  case Text(String)
  case Unicode(String, Int)

  fn static unicode(value: String) -> Node {
    # `value.chars` returns an iterator over the extended grapheme clusters,
    # and `count` simply counts them.
    Node.Unicode(value, value.chars.count)
  }
}

使用这种方法，我们构造 Unicode 节点如下：

Node.unicode('this is the string to render')

空格和缩进

为了处理空格和缩进，我们将定义三个节点： SpaceOrLine,
Line，和 Indent。

SpaceOrLine 是一个节点，如果它驻留在不需要换行的组中，则渲染为空间，换行时渲染为线是需要。

Line 是一个节点，如果它位于需要换行的组中，则呈现为新行，否则呈现为空。

Indent(nodes) 是一个渲染一个或多个节点的节点，缩进每个新行，但前提是它位于需要换行的组中。

在 Inko 中，我们像这样定义这些节点：

class enum Node {
  ...
  case SpaceOrLine
  case Line
  case Indent(Array[Node])
}

为了帮助理解这些节点以及何时使用它们，请考虑我们要格式化的以下数组：

我们将构建以下树来格式化该数组：

# I'll explain what "Group" is in just a moment.
Node.Group(
  0,
  [
    Node.Text('['),
    Node.Line,
    Node.Indent(
      [
        Node.Text('100'),
        Node.Text(','),
        Node.SpaceOrLine,
        Node.Text('200')
      ]
    ),
    Node.Line,
    Node.Text(']')
  ]
)

当不需要包装时，数组将按原样呈现，因为 Line 化为乌有， Indent 仅在需要包装时才缩进，并且
SpaceOrLine 渲染到一个空间。缠绕时是需要时，数组呈现如下：

分组节点

要将节点分组在一起，我们可以使用两个节点之一： Group 或者 Nodes。

Group(id, nodes) 是我们尝试适应当前行的节点集合。如果这不合适，每个子节点都会放置在自己的行上。每个组都有一个 ID（只是范围内的数字） 0 <= id <= N) 对于我们正在格式化的文档来说是唯一的。

筑巢时 Group 节点（例如 Group -> something else -> Group），按组检查是否需要包装。这意味着如果一个外部
Group 需要换行，这不会立即强制所有子组也换行。

Nodes(nodes) 是我们直接渲染的节点集合，无需任何特殊处理。这使得在代码方面更容易使用某些辅助函数来生成我们只想连接在一起的多个节点。

我们这样定义这些节点：

class enum Node {
  ...
  case Group(Int, Array[Node])
  case Nodes(Array[Node])
}

这 Int 参数是组 ID，而 Array[Node] 参数存储子节点。

构建时 Group 我们需要跟踪下一个要使用的节点 ID。这是通过在某处存储一个计数器，将现有值作为新值来完成的。 Group，然后递增它：

let id = the_id_counter

the_id_counter += 1
Node.Group(id, nodes)

在 Inko 中，我们可以将其缩短为以下内容：

Node.Group(the_id_counter := the_id_counter + 1, nodes)

这 := 运算符为变量分配一个新值，并返回之前的值。相比之下， = 运算符丢弃旧值。

条件格式

我们要介绍的最后一个节点是 IfWrap(id, A, B) 节点。如果组使用 ID，则这是呈现节点 A 的节点 id 需要被包装，否则渲染节点B。

使用前面显示的数组示例，当需要使用此树进行换行时，我们可以使用此节点添加尾随逗号：

Node.Group(
  0,
  [
    Node.Text('['),
    Node.Line,
    Node.Indent(
      [
        Node.Text('100'),
        Node.Text(','),
        Node.SpaceOrLine,
        Node.Text('200'),
        Node.IfWrap(0, Node.Text(','), Node.Text(''))
      ]
    ),
    Node.Line,
    Node.Text(']')
  ]
)

当需要包装时，数组现在呈现如下：

计算宽度

在格式化树时，我们需要知道一个节点在当前行占据了多少个字符，因为这用于确定是否需要换行。这意味着我们需要一种方法来计算 a 的宽度 Node，我们将其定义如下：

class enum Node {
  ...

  fn width(wrapped: ref Set[Int]) -> Int {
    match self {
      case Nodes(nodes) or Group(_, nodes) or Indent(nodes) -> {
        Int.sum(nodes.iter.map(fn (n) { n.width(wrapped) }))
      }
      case IfWrap(id, node, _) if wrapped.contains?(id) -> node.width(wrapped)
      case IfWrap(_, _, node) -> node.width(wrapped)
      case Text(str) -> str.size
      case Unicode(_, chars) -> chars
      case SpaceOrLine -> 1
      case _ -> 0
    }
  }
}

这 wrapped 参数是一个不可变的借用哈希集，其中包含我们迄今为止已处理且需要包装的所有组的 ID。返回值是整数宽度。在正文中，我们针对当前节点进行模式匹配（self）。对于包含其他节点的节点，例如 Nodes
和 Group，宽度是所有子节点的宽度之和。

为了 IfWrap 我们必须根据是否需要包裹来不同地计算宽度。这也是为什么我们不能计算一次宽度并缓存它：深度嵌套节点的宽度可能会根据父节点的包装需求而改变。

为了 Text 我们用 String.size 获取以字节为单位的大小（这恰好也是它的字符数，如 Text 节点仅存储 ASCII 文本），而对于
Unicode 我们使用预先计算的字素簇计数的节点。

该实现是一种递归算法而不是迭代算法，主要是为了简单起见，并且因为格式化树通常不是那么深度嵌套，所以它已经足够好了。

最终结果如下：

class enum Node {
  case Group(Int, Array[Node])
  case Nodes(Array[Node])
  case IfWrap(Int, Node, Node)
  case Text(String)
  case Unicode(String, Int)
  case SpaceOrLine
  case Line
  case Indent(Array[Node])

  fn static unicode(value: String) -> Node {
    Node.Unicode(value, value.chars.count)
  }

  fn width(wrapped: ref Set[Int]) -> Int {
    match self {
      case Nodes(nodes) or Group(_, nodes) or Indent(nodes) -> {
        Int.sum(nodes.iter.map(fn (n) { n.width(wrapped) }))
      }
      case IfWrap(id, node, _) if wrapped.contains?(id) -> node.width(wrapped)
      case IfWrap(_, _, node) -> node.width(wrapped)
      case Text(str) -> str.size
      case Unicode(_, chars) -> chars
      case SpaceOrLine -> 1
      case _ -> 0
    }
  }
}

跟踪包装需求

当遍历格式化树时，我们需要记录特定子树是否需要换行。为此，我们将引入一个 Wrap 枚举可以处于两种状态之一： Enable，意味着需要包装，或者 Detect
这意味着我们需要根据宽度来检测它。 Detect 是默认状态：

class enum Wrap {
  case Enable
  case Detect

  fn enable? -> Bool {
    match self {
      case Enable -> true
      case _ -> false
    }
  }
}

这 Wrap.enable? 添加方法是为了更容易检查是否需要换行，而无需手动进行模式匹配 Wrap
枚举。

将 AST 降级为格式化树

要将 AST 降级为格式化树，我们需要一种类型来访问 AST 中的节点并返回其对应的节点 Node 价值观。我们还需要一个类型 Node 并将其转换为字符串格式的源代码，同时跟踪必要的状态，例如行长度。为此，我们将介绍两种类型： Builder 和 Generator。

这 Builder type 用于定义访问 AST 节点所需的方法，返回其对应的 Node 价值观。这 Generator type 用于转换那些 Node 值到字符串。

为了简单起见，我们将限制本文中显示的代码来处理简单的函数调用、文本文字和字符串。

发电机类型

的基本布局 Generator 类型如下：

class Generator {
  # This field is the buffer we'll write our formatted code into.
  let @buffer: StringBuffer

  # This field tracks the indentation levels, not the number of indentation
  # characters (i.e. if you use 2 spaces for indentation, you increment this
  # field by one).
  let @indent: Int

  # The number of characters/extended grapheme clusters on the current line.
  let @size: Int

  # The maximum number of characters we allow per line. If your formatter
  # doesn't allow users to change this value, you probably want to turn this
  # into a constant instead.
  let @max: Int

  # A hash set containing all the groups that need to be wrapped.
  let @wrapped: Set[Int]

  fn static new(max: Int) -> Generator {
    Generator {
      @buffer = StringBuffer.new,
      @indent = 0,
      @size = 0,
      @max = max,
      @wrapped = Set.new,
    }
  }
}

StringBuffer 是我们可以推送的类型 String 中的值并连接在一起，而不产生中间 String 价值观。

为了使用这种类型，我们定义一个 generate 方法需要一个 Node，将其呈现为 String 并存储 String 在缓冲区中的 Generator 类型：

class Generator {
  ...

  fn mut generate(node: Node) {
    node(node, ref Wrap.Detect)
  }

  fn mut node(node: Node, wrap: ref Wrap) {

  }
}

这 generate 方法只是调用 node 方法的默认值
wrap 争论。如果您选择的语言支持默认参数，则不需要这样做，您可以将这两个方法合并为一个方法。

Inko 使用单一所有权进行内存管理。这 generate 方法接管了所有权 Node 传递给它，因为的类型 node
论据是 Node 而不是例如 ref Node （这是不可变的借用）。表达方式 ref Wrap.Detect 创建一个实例 Wrap.Detect case，然后将该值的不可变借用传递给 node 方法。这个借用一直有效，直到我们从调用返回 node。

在我们实施之前 node 方法，我们将添加两个辅助方法
Generator 输入并定义一个包含用于缩进行的字符的常量：

let INDENT = '  '

class Generator {
  ...

  fn mut text(value: String, chars: Int) {
    @size += chars
    @buffer.push(value)
  }

  fn mut new_line {
    @size = INDENT.size * @indent
    @buffer.push('n')
    @indent.times(fn (_) { @buffer.push(INDENT) })
  }
}