剖析千行C语言文本编辑器Kilo的技术细节
今天上午学习了一下Kilo的源代码。我很早以前就对文本编辑器的实现方法感兴趣了。
Kilo是一个很简易却不简陋的项目，清晰地展示了如何构建一个终端下的文本编辑器，它的目的不是真正让你学会去开发一个高标准高质量，能投入使用的文本编辑器，而是理解文本编辑器的核心骨架、理解一个看似庞大一团糟的问题的拆解思路。这是一个很好的起点。也过了一把爽玩C语言的瘾（虽然我并没有写几行代码）。
程序分析
整个项目只有一个文件，一千三百行代码。我用了大概一个半小时梳理了程序的执行流程，手画了一个流程图。为了美观，我又用Graphviz绘制了一个电子版：
这张图我省略了一些深的函数调用，但也能帮助我大体上掌握这个程序的执行流程。结合这张图与源码，我发现文本编辑器的核心功能——打开、编辑、保存，实现难度并不大，在C语言中容易踩坑的是缓冲区处理、文件读写这种老生常谈的内容。在这个程序中，调用最多、最重磅的部分是initEditor这个函数，以及后续的高亮处理，尤其是前者在窗口尺寸计算、修改后的做法上花费了大功夫。其实和终端环境的交互才是最麻烦的点，它提供的封装和抽象并不多，有很多需要自己手动调试的地方，繁琐是显著特征。
终端信号处理
我发现在终端程序里，需要快捷键的部分都是使用Raw mode和signal相关的函数组合实现的，在理解signal这个函数和它的有关宏的概念时，耗费了比较长的时间。
简单来说，signal用于处理用户在终端发出的信号，比如SIGINT代表由C-c产生的中断信号，SIGIGN代表忽略信号，即接受到这个信号以后什么都不做，关于如何接受信号，就要说起signal()这个函数。定义如下：
void (*signal(int sig, void (*func)(int)))(int);
看起来非常复杂，说人话就是接受两个参数，第一个参数是int类型的sig，是信号编号，比如SIGINT，这是要接收的信号。第二个参数是一个函数指针，接受一个返回void，参数是int类型的信号处理函数，使用第二个函数中的函数对接受到的信号做处理。函数返回原来的信号处理函数（函数指针）。
可以用typedef简化理解：
// 定义信号处理函数的类型
typedef void (*sighandler_t)(int);
// 用 typedef 重写 signal 声明
sighandler_t signal(int sig, sighandler_t func);
在Kilo中，C-c是被忽略的，因为它非常容易导致丢失修改，可以这样实现：
signal(SIGINT, SIGIGN);
不过，在Kilo的实现，是通过调用editorReadKey()，从Raw Mode 中读取一个按键存入数组，用switch匹配按键对应的值再返回给调用方，调用方也通过switch，匹配对应的操作函数。而在C-c的部分，则是直接break掉了。
...
case CTRL_C: /* Ctrl-c */
/* We ignore ctrl-c, it can't be so simple to lose the changes
* to the edited file. */
break;
...
这种实现方法也有一定局限性，不同的终端模拟器可能发送不同的转义字符，硬编码转义字符会出现不适配的情况。并且使用read()阻塞读取输入有性能瓶颈。
精妙的数据结构与算法
这个程序最有趣的地方在于清晰、通用的数据结构的设计，以editorConfig为例：
struct editorConfig {
int cx, cy; /* Cursor x and y position in characters */
int rowoff; /* Offset of row displayed. */
int coloff; /* Offset of column displayed. */
int screenrows; /* Number of rows that we can show */
int screencols; /* Number of cols that we can show */
int numrows; /* Number of rows */
int rawmode; /* Is terminal raw mode enabled? */
erow *row; /* Rows */
int dirty; /* File modified but not saved. */
char *filename; /* Currently open filename */
char statusmsg[80];
time_t statusmsg_time;
struct editorSyntax *syntax; /* Current syntax highlight, or NULL. */
};
我们定义了一个editorConfig类型的变量，它全局唯一，维护了程序的基本状态，包括行、列、滚动偏移、终端尺寸。让程序状态的流转非常清楚。这些内容都是一个文本编辑器需要关心的最核心内容：光标位置、视图偏移、数据和文件的状态等信息。
通过这个结构体，能简单地获取程序当前的状态，或者为某项功能对状态作出修改，对一个新手来说还是挺拓宽思路的，至少我想不到怎么设计这些数据结构。
数据与显示的分离
在editorConfig中嵌套了一个erow类型的变量，里面的东西也可以展开说说，定义如下：
typedef struct erow {
int idx; /* Row index in the file, zero-based. */
int size; /* Size of the row, excluding the null term. */
int rsize; /* Size of the rendered row. */
char *chars; /* Row content. */
char *render; /* Row content "rendered" for screen (for TABs). */
unsigned char *hl; /* Syntax highlight type for each character in render.*/
int hl_oc; /* Row had open comment at end in last syntax highlight
check. */
} erow;
这里面有一个render字段，在editorUpdateRow()中，有这样的代码：
unsigned int tabs = 0, nonprint = 0;
int j, idx;
/* Create a version of the row we can directly print on the screen,
* respecting tabs, substituting non printable characters with '?'. */
free(row->render);
for (j = 0; j < row->size; j++)
if (row->chars[j] == TAB)
tabs++;
unsigned long long allocsize =
(unsigned long long)row->size + tabs * 8 + nonprint * 9 + 1;
if (allocsize > UINT32_MAX) {
printf("Some line of the edited file is too long for kilo\n");
exit(1);
}
循环的if中使用的 TAB 定义在KEY_ACTION枚举，值为9，在ASCII码中是\t也就是水平制表符。代码在统计tab的数量。
问题在于，一个\t在内存中占1字节，但在屏幕显示的时候会占据八个字符的宽度，这里就体现出render的作用了，如果一行有两个\t，每个最多展开为八个空格，那么所需要计算的大小就是2 * 8 + chars的大小：
(unsigned long long)row->size + tabs * 8 + nonprint * 9 + 1;
那个恒为0的变量nonprint可能是为将来打印不可见字符设计的。结尾的+1为'\0'预留。
按照这个公式，给render分配内存：
row->render = malloc(row->size + tabs * 8 + nonprint * 9 + 1);
随后，这些代码在非制表位填充空格：
idx = 0;
for (j = 0; j < row->size; j++) {
if (row->chars[j] == TAB) {
row->render[idx++] = ' ';
while ((idx + 1) % 8 != 0) // 在非制表位填充空格
row->render[idx++] = ' ';
} else { // 正常字符直接赋值
row->render[idx++] = row->chars[j];
}
}
row->rsize = idx; // 在循环结束的时候，idx等于写入字符总数
row-render[idx] = '\0'; //在字符末尾添加结束符
虽然有点绕，但设计还是非常巧妙的！
代码高亮
源码中使用大量篇幅实现了代码高亮，定义了一些关键字：
char *C_HL_extensions[] = {".c", ".h", ".cpp", ".hpp", ".cc", NULL};
char *C_HL_keywords[] = {
/* C Keywords */
"auto", "break", "case", "continue", "default", "do", "else", "enum",
"extern", "for", "goto", "if", "register", "return", "sizeof", "static",
"struct", "switch", "typedef", "union", "volatile", "while", "NULL",
/* C++ Keywords */
"alignas", "alignof", "and", "and_eq", "asm", "bitand", "bitor", "class",
"compl", "constexpr", "const_cast", "deltype", "delete", "dynamic_cast",
"explicit", "export", "false", "friend", "inline", "mutable", "namespace",
"new", "noexcept", "not", "not_eq", "nullptr", "operator", "or", "or_eq",
"private", "protected", "public", "reinterpret_cast", "static_assert",
"static_cast", "template", "this", "thread_local", "throw", "true", "try",
"typeid", "typename", "virtual", "xor", "xor_eq",
/* C types */
"int|", "long|", "double|", "float|", "char|", "unsigned|", "signed|",
"void|", "short|", "auto|", "const|", "bool|", NULL};
然后在具体实现editorUpdateSyntax()中，简单粗暴地遍历字符匹配这些关键字。在一般的教学例子中这样实现是可以的，我认为在具体的工程中应当用词法分析、语法分析和字典树去匹配。更易于维护和拓展，也能适配复杂的嵌套。
上述分析提到的缺点都可以作为优化方向，比如提供更简单操作接口，用词法分析技术或接入LSP服务器，为程序提供Lua接口来扩展插件……不过我相信在古老的纯C应用中，添加这些功能的繁琐程度和开发周期简直是灾难级别的。但是在处理快捷键上，使用termcap库的难度应该小于修改代码高亮部分的难度。
这个项目最值得学习的点是如何将抽象的功能和终端联系起来、如何设计合理的数据结构以及标准库的使用。是阐释「程序 = 数据结构 + 算法」的很好例子。不过我自己是想不到那些函数该什么时候用，没准还会手动实现标准库造好的轮子呢。
学习的过程很好玩，从主函数开始探索整个程序，一段一段地跳转调用，A调用B，B调用C，C调用D，理解了逻辑后再把它们画成图，对感兴趣的部分深入研究，有一种前人用他的智慧抚平我大脑褶皱的感觉……读懂它，几乎就等于一只脚趾踩上了理解Vim / Nano等项目的大门吧。
想自己重新实现一次，然后加入自己的优化，比如联动Lua / Zig甚至是Go来实现上层的功能，好玩好玩真好玩。
头皮好痒，要长脑子了！