前言

C语言课程设计有一道实现一个文本文件编辑器的题目，本以为是个小程序，了解之后才发现入了大坑。做一个文本编辑器显然是一个重复造轮子的行为，更何况是一个命令行文本编辑器，因而网上能够找到的教程及资源十分有限。用5天时间肝完了这一课设题目，趁这么一个机会，为中文网贡献一份简易文本编辑器教程。

最终实现效果：一个类似于Vim界面的简易跨平台文本编辑器。

项目源码已上传至Github。

以下内容按照实验报告要求撰写。

实验内容

实现一个具有以下功能的文本文件编辑器：

能够打开文本文件、保存文本文件
能够从文本文件中读入文本，并在内存中以适当的数据结构进行储存
能够对储存在内存中的文本进行高效编辑
能够支持基本的快捷键操作

实验方案

分析实验内容及目标，我们将程序分为前后端，后端处理文本数据结构的编辑、文件操作，前端控制文本显示、光标的操作与移动。我的程序设计思路为：先后端、再前端。因此，接下来我将依次从选取技术栈、文本数据结构、文件处理、光标控制与移动展开叙述。

选取技术栈

后端的数据处理只需依赖C标准库，同时也应当只依赖非平台特性的C函数进行实现，以更好地支持跨平台特性。出于同样的跨平台考虑，程序采用Curses库编写前端。由于不同平台下Curses库的实现完成度不同，我在不同平台下使用了不同的Curses开源实现——Windows下使用PDcurses，Unix/Linux下使用ncurses。

项目使用CMake进行管理，这样能够很方便地通过Makefiles进行跨平台编译项目。通过编译时判断平台，选择相应的Curses开源实现库进行编译或链接。

include_directories(./include)

aux_source_directory(./src DIR_SRCS)

add_executable(Notepad main.c ${DIR_SRCS})

if(WIN32 OR MSVC)
        add_definitions(-DPDC_WIDE)
        # PDcurses通过增加PDC_WIDE宏定义开启宽字符支持
        # 详见其官方install说明及Makefiles文件
        add_subdirectory(./include/pdcurses)
        target_link_libraries(Notepad
                PRIVATE
                PDcurses
        )
else(UNIX)
        find_package(Curses REQUIRED)
        # 本地已编译安装了ncurses
        include_directories(${CURSES_INCLUDE_DIRS})
        target_link_libraries(Notepad ${CURSES_LIBRARIES})
endif()

项目结构如下：

│   CMakeLists.txt
│   main.c // 程序入口
│
├───build // Makefiles
├───include // 头文件及第三方引用
│   │   console.h // 前端
│   │   file.h // 文件处理
│   │   line.h // 文本数据结构及其操作
│   │   page.h // 文本文件抽象
│   │
│   └───pdcurses // PDcurses源码
├───out
│   ├───unix
│   └───win32
└───src // 源文件
        console.c
        file.c
        line.c
        page.c

文本数据结构

文本数据结构是该程序的核心，直接关系到文本操作流畅与否。为了了解目前业界可行的文本数据结构及编辑算法，我进行了一番简单的调研，了解到了两个著名的文本数据结构：Gap Buffer（Emacs）、Piece Tables（Word、VScode）。同时，参考Charles Crowley在1998年发表的论文《Data Structures for Text Sequences》（图2-2-1），比较学习了各大现有文本数据结构的优劣，最终选择了Gap Buffer作为该程序的文本数据结构实现。

一个很自然的存储文本的想法就是使用顺序表结构进行字符存储，但这种数据结构会使得编辑变得十分困难。每一次对文本中间的字符进行插入、删除操作时，都会引起其后面所有字符的位移，最坏时间复杂度可以达到O(N)，这是不可忍受的。

编辑文本的高时间复杂度是由后续数组元素的整体位移引起的，因此，一个容易想到的解决方式就是减少数组元素的位移次数。如果我们在待操作的位置上横跨一个具有一定长度的空数组（图2-2-2），它将顺序表拆分成了两部分，在该数组上进行的操作就不会引起其它两部分元素的移动。因此，我们可以将文本的插入与删除操作都在该数组上进行，此时，文本修改的时间复杂度就可以下降至O(1)。

Buffer数组的长度是有限的，当其填满后，就需要重新申请内存。重新扩容并插入文本无疑是十分耗时的，它至少需要遍历一遍文本，这一过程的时间复杂度为O(N)。因此，我们应当设置合理的Buffer数组长度，以尽可能地减少其扩容次数。当然，由于每当我们删除一个字符，Buffer的容量也会相应增加，所以在实际应用中，扩容的次数其实是相当之少的。然而，在打开文件读入文本时，因扩容而导致的低效影响十分明显，我们将在后面的测试环节中对其进行讨论。

Gap Buffer的具体工作原理图如下（图2-2-3）：

前端光标的移动，实质就是buffer在数组中的移动（图2-2-4）。而buffer在数组中的每一次移动，只需要交换其首尾两个元素，时间复杂度也是O(1)的。当然，从头移动到尾需要遍历一遍数组，达到线性时间复杂度，可在实际应用中，光标的移动总是发生在相邻几个元素或相邻几行之间，这使得Gap Buffer在大部分应用场景下是十分可靠的。

在初次设计时，我考虑将文本的每一行使用Gap Buffer数据结构进行存储，将每一行使用链式数据结构进行连接。然而，在后续的前后端衔接中发现，这样的设计将难于进行光标定位，物理光标与逻辑光标之间的关系很难建立起来。于是，我最终选择将整个文本以一个Gap Buffer结构进行存储。

在该程序中，文本数据结构称为line，它是Gap Buffer及其相关操作的实现；文本文档抽象为page，同一时间只有一个page实例，其包含一个line属性及其它文本文件的相关信息。

文件处理

读取文件时，先将文本内容整块读入一个足够大的缓存区（动态数组），再从头遍历该缓存区，将文本通过统一的数据结构接口插入。这样操作的时间复杂度为O(2N)，在实际测试中，面对大文件，打开速率仍能超过Windows自带的记事本（当然它考虑了编码问题），日常应用感受不到两次遍历带来的性能差距。我们将在稍后的测试环节中进行讨论。

光标控制与移动

光标坐标关系的确立

前端的光标操作应当时刻与后端数据结构的逻辑光标操作同步，这意味着，我们需要建立起前端物理光标与后端逻辑光标的坐标对应关系（从二维映射到一维）。如果我们将终端的每一个小格视为一个字符，其占用了后端数据结构的一个字符，那么，根据当前视图行首距离文档行首的偏移量大小offset、物理光标坐标(x,y)，就可以计算得到光标所指的位置是文本中的第几个字符。

我将文本中的“第几个字符”定义为计数位置（Count Position）。计数位置是不受Buffer数组移动影响的，当一个字符被插入或删除时，它在这个文本序列中的计数位置是一定的。这个特性能够很好定位每一个字符，因而在该程序中，对文本数据结构的几乎每一项操作接口都是基于计数位置进行的。

字符在数组中进行存储，我们可以通过数组下标访问他们。但需要注意的是，由于Gap Buffer的存在，每一个字符的下标实际上是动态变化的。Gap Buffer长度的变化、位置的移动都会影响每一个字符的数组下标。

我将数组下标定义为Buffer Position。当需要涉及对文本数据结构的底层操作，或操作需要逻辑光标的参与时，Buffer Position将派上用场。由于Buffer数组的长度始终已知，Buffer Position与Count Position之间可以很轻松的建立转换关系，物理光标与逻辑光标的坐标得以很好地统一起来。

光标移动处理与显示

想让上述坐标关系建立的必要条件，就是终端的每一个小格都必须视为一个字符。将二维映射至一维，我们需要通过插入标记字符来标识每一行的结尾与终端部分空白位置的不可达状态。这样，物理光标坐标在完成计算后，直接通过坐标转换寻址到文本数据结构，判断该位置的有效性，从而做出相应的移动操作。

在该程序中，每一行的结尾加入了NEWLINE标识，并从该标识开始至终端边框处，每一个小格都填充了INVALID标识。在文档的结尾处，加入了END标识。相应的，前端根据后端数据结构进行画面渲染时，也会将相应的标识翻译为对应的转义字符。如遇到NEWLINE标识则输出\n、遇到INVALID标识则跳过输出。

关键功能模块的流程图

难点及其解决方法

我在实际操作中，主要遇到了以下难点：光标坐标关系的建立、读取文件时内存泄漏、中文支持。

光标坐标关系的建立

问题描述

尽管在实验方案中，我提出了基于Count Position和Buffer Position概念而实现的坐标关系建立方案，但这是在项目中期之后才意识到的问题并提出的解决措施（图4-1-1-1）。

在此之前，我始终在函数接口中混用数组下标与计数位置，部分计算函数使用了数组下标作为参数，而在另一些计算函数中，却又在不知不觉中使用了后来提出的所谓计数位置进行运算。在这样的条件下，映射到一维的坐标转换出现了问题（却又并非总是出错），这就导致每增添一个物理光标功能，就需要一段长时间的debug调参，强行使得转换函数正常工作。

解决思路和方法

如上文所述，明确地定义各坐标在程序中的含义，重新构建文本数据结构基本操作函数及光标控制函数。即确定了Buffer Position与Count Position的含义，将文本数据结构基本操作函数以Count Position为基准重写。

关键代码

Buffer Position与Count Position之间的转换代码如下：

int bpos_to_cpos(Line *line, int bpos)
{
    if (bpos <= line->cursor_pos)
        return bpos + 1;
    else
        return bpos - line->gap_length + 1;
}

int cpos_to_bpos(Line *line, int cpos)
{
    int t_p = bpos_to_cpos(line, line->cursor_pos);
    if (cpos < t_p)
        return cpos - 1;
    else
        return line->cursor_pos + line->gap_length + cpos - t_p;
}

Count Position与前端物理光标坐标的转换代码如下：

void get_cursor_pos(int offset, int pos, int *y, int *x)
{
    // y begin at position 1
    *y = pos / page.cols + 1 - offset;
    *x = pos - (*y - 1 + offset) * page.cols;
}

解决效果

效果很好，后续功能的添加十分轻松。

读取文件时内存泄漏

问题描述

当我尝试打开一个大小约为85MB的文本文件时，程序直接崩溃。通过debug，很轻松地找到了问题所在——我把扩容时使用的临时数组开在了栈内存中。重新修改后，再次打开文件，我的电脑风扇开始猛烈地转了起来（图4-2-1-1）。

打开一个文本文件所消耗的内存甚至超过了跑赛博朋克，程序显然发生了内存泄漏。然而，排查C语言的内存泄漏不是什么容易的事情。

解决思路和方法

由于程序体积不大，整个程序调用了与手动申请内存有关的相关操作的地方不过只有两处动态数组扩容。于是，我先将两处缓存数组的初始大小调整为大于文本字符数，从而确保在读取过程中不会发生扩容操作。

这样一番操作后，打开同一文件的内存占用只有477MB了。内存泄漏的原因基本可以定位在扩容函数中。

将扩容函数中使用到的临时数组及时释放，将缓存数组的初始大小置回原始值，重新打开同一文件，此时内存占用8G，比第一次测试减少了4G的内存占用。显然，扩容函数中仍然有地方没有释放内存。

注意到此时与内存申请相关的，只有calloc函数的使用，于是我进行了一次实验（图4-2-2-1），以确定是否在重新通过calloc函数申请内存后，原数组内存没有被释放。

实验结果显示，重复调用calloc函数并不会释放原内存块，使得原内存块发生内存泄漏。因此，调用前应当使用free函数先行释放原内存块的内存。

修改之后的结果显示，整个文本文件读取过程的内存占用没有超过200MB，在完成读取后，内存占用稳定在了88.8MB，与文本文件的大小基本一致，内存泄漏得以修复。

关键代码

注释的两行即为关键代码。

void grow_read_buffer()
{
    int old_length = buffer_length;
    old_buffer = (wchar_t *)calloc(old_length, sizeof(wchar_t));
    memcpy(old_buffer, read_buffer, old_length * sizeof(char));
    free(read_buffer); // free before calloc
    read_buffer = (wchar_t *)calloc(buffer_length * 2, sizeof(wchar_t));
    buffer_length *= 2;
    for (int i = 0; i < old_length; i++)
        read_buffer[i] = old_buffer[i];
    free(old_buffer); // free after using
}

解决效果

效果很好，在打开900+MB的文本文件时，不会因为内存占用过高而被操作系统杀掉了。

中文支持

问题描述

Curses库支持宽字符的输入与输出，于是我考虑使程序支持Unicode编码，从而获得中文支持。然而，在将整个数据结构切换至宽字符后，尽管能够以UTF-8编码正确地读取文本文件中的中文字符，也能够用C标准库的宽字符输出函数进行打印，但一旦切换至Curses库控制下的终端，则会出现多列Unicode字符打印失败的问题。

具体表现为，使用Curses库的addwch等宽字符输出函数输出多列字符时，其在终端上的占用只有一列，即只输出了一半中文，从而导致前端与后端的同步也不一致了。

解决思路和方法

最初，根据curses.h的注释提示（图4-3-2-1），我在curses.h中手动添加了PDC_WIDE宏定义进行编译，以开启宽字符输入输出函数，因此，起初我认为是Curses的宽字符支持未正确开启而导致的，即只开启了函数声明而未开启实现。

因此，我重新阅读了PDcurses的源码结构及官方自带的install说明（图4-3-2-2）与Makefiles文件（图4-3-2-3）。于是发现，PDC_WIDE的宏定义应当在编译时作为参数指定（虽然似乎其它实现源文件也会include该头文件从而引入宏定义，但我不确定是否会有影响）。

重新编译之后，问题没有得到解决。于是，我开始寻找Curses库对于Unicode字符及多列字符输出的有关资料。令人沮丧的是，中文网上对于Curses的相关资料少之又少，只有重复复制的少量几篇文章，且没有任何有价值的信息。而在外网上，我可以找到大量使用宽字符输出函数输出Unicode字符的样例（图4-3-2-4），在我的程序上，使用这些方法（图4-3-2-5）可以使我正确地输出单列Unicode字符（事实上我先前的代码也能如此工作）。但无一例外，它们都无法在我的机器上输出多列字符（如中文字符），也似乎没有人对使用Curses输出中文字符感到兴趣。

我找到了一篇Curses接口规范及说明的文档（图4-3-2-6），阅读了其中有关输出字符的说明。了解到，使用addch函数就可以输出任意编码格式的字符，而事实上，该函数的形参也是一个chtype型的变量，这是一个包含了16位attribute信息与宽字符信息的类型（类似于位掩码）。同时，根据文档中的描述，该函数本身就能够正常支持多列字符（multi-column character）的输入。

在尝试将字符包装成为chtype类型并调用addch函数输出后，问题仍未得到解决，多列字符仍然未能正确地输出。至此，我将该问题定性为PDcurses的实现bug，搁置解决。

程序测试

测试用例

下图为测试用例及测试情况（图5-1-1）

文件打开测试

下图为不同Gap Buffer默认长度打开文本文件所需的时间对比（图5-2-1）。需要注意的是，打开速度为0表示耗时过长，不作计时。

可见，选择适当的Gap Buffer默认长度能够有效地提高程序读取文本文件的速率。当然，过高的长度在文本文件较小的时候会造成内存资源的浪费。由于日常编辑的文本文档不会超过10MB，我最终将默认长度定在了500000字节的大小。

总结和展望

通过本次程序设计实验，我学会了如何使用CMake管理一个C工程项目、组织项目源文件，初步了解了编译、链接的过程。同时，学习了基本的文本编辑数据结构，获得了运用Curses库控制终端输入输出的能力。这次程序设计实验带给我最大的教训，就是在明确定义、设计好模块前便开始编写代码，这使得我在实现光标坐标转换模块下耗费了大量的时间。另外，我仍没有弄清楚如何将静态库与动态库包含在程序源码中通过CMake链接，因而采用了编译及预先安装库的方式引入第三方库，这不太优雅。

该程序的下一步发展计划，是实现对中文输入输出的支持，即完全支持Unicode编码字符（阿拉伯语等倒序字符除外）。同时，尝试使用多Gap Buffer+多线程的方式进一步优化文本编辑器读取文本文件的速度。多Gap Buffer也能对逻辑光标在序列中的移动起到优化作用，这对于实现全文本搜索功能是具有重要意义的（搜索往往需要跨度较大的光标移动）。