木兰重生：木兰代码格式化之自动调整缩进的 150 倍性能优化

节选：

本项目旨在重现「木兰」编程语言的语法和功能，已开源在码云。所有例程演示的语法可以用原始的木兰可执行文件 ulang-0.2.2.exe 检验。如发现有异烦请告知，定将礼谢。

本文介绍的是个临时起意的副线任务，但也是木兰编程语言生态建设的一步。

缘由

前两天为了做井字棋游戏，中文化了一个例程，并从中截取了绘制棋盘的部分代码，改写成了木兰代码，打算在此基础上进一步开发。

代码很短，三十多行，也抛出了预期效果如下：

问题是，由于是随手拷贝自 Python 源码，也没有特别注意保留行头空格（当然也仗着木兰对缩进量不敏感），导致代码缩进非常参差不齐，见下图左侧：

虽然手工调整缩进不用几分钟，但因为马上就想到可以用木兰交互环境获取未配对的括号数的机制来实现自动缩进，忍不住在自制编辑器中集成了这个功能，实现挺方便（因为有之前的高亮部分打底），格式化效果也如预期见上图右侧。

原始方案

基本思路请看十五行木兰源码：

func 格式化(源码) {
  缩进单位 = "  "
  所有行 = 源码.splitlines()
  部分源码 = ""
  格式源码 = ""
  // TODO: 每行的缩进量由当前行之前的代码决定, 复杂度为 N^2 (N 为代码行数)
  for 行号 in 1..len(所有行) {
    当前行 = 所有行[行号 - 1]
    部分源码 += 当前行
    各代码段 = 解析(部分源码)
    缩进数 = 未配对括号数(各代码段)
    格式源码 += 缩进数 * 缩进单位 + 当前行.strip() + "\n"
    部分源码 += "\n"
  }
  return 格式源码
}

但这个 N^2 的复杂度如鲠在喉。起初由于那个棋盘代码只有 34 行，运行格式化还能接受（后测大约 240 毫秒），就有先放着不管的打算，但手贱跑了一下至今项目内最长的木兰源码文件——318 行的“儿歌.ul”，结果跑了 12 秒多才完成不说还报个神奇的警告：

2020-10-04 11:48:03.095 Python[40873:15785576] IMKClient Stall detected, *please Report* your user scenario attaching a spindump (or sysdiagnose) that captures the problem - (imkxpc_bundleIdentifierWithReply:) block performed very slowly (8.90 secs).

是可忍孰不可忍。于是着手改为 N 复杂度。结果，之前留的一个雷还是踩上了。