做编辑器内核这些年我发现一个特别有意思的现象很多人聊起GapBuffer都觉得它无非就是“一块数组开个口子插入删除少挪数据”原理简单到可以随手写出。可真把GapBuffer放进一个带语法高亮、代码折叠、书签、光标的完整编辑器里真正折磨人的从来不是gap本身而是围绕它长出来的一大堆标记——也就是Mark的维护问题。GapBuffer的高效写入能力和文本标记位置的正确性天生就是一对矛盾。文本一变所有记在旧位置上的标记全部作废。如果你靠“每次编辑后遍历所有标记逐个偏移”的笨办法能把一个输入法连续敲字的过程卡出掉帧动画。这篇文章我想聊聊我在这类标记管理上的完整思路锚点规则、区间增量树、批量事务通道以及那些踩过之后才明白的坑。内容适合正在写编辑器、IDE插件、日志高亮、富文本内核的开发者参考也适合对文本数据结构有兴趣、想理解“标记到底怎么跟文本一起走”的人。1. GapBuffer到底卡在哪一次插入引发的标记漂移1.1 从逻辑位置到物理偏移gap是怎么“背叛”标记的先快速过一遍GapBuffer的结构。它本质上一个内存块里开了个“空腔”空腔左边是已确认的文本head右边是tail。光标在哪个位置空腔就被挪到那个位置挪动方式是一次memmove把尾段数据平移。插入文本时写入空腔中删除文本时如果删除范围覆盖到空腔边缘就调整空腔的起点和终点。这套方案最大的好处是局部写入的代价极低尤其是连续输入时gap一直停在光标附近每次按键几乎只是往间隙里填字符。但问题在于文本的“逻辑位置”和它在数组里的“物理下标”之间隔着一层gap的距离。举个例子。假设缓冲区里有ABCDEF六个字符gap不在任何地方时A的物理下标是0、E的下标是4。如果我想在E之前插入xyz需要先把gap移动到E的位置。移动完的瞬间数组物理分布变成了AB CD 下划线区 xy 下划线区不对准确说是head是ABtail是CDEFgap就在B和C之间。E此刻的物理下标变成了5比原来的4偏了一位。标记“E字符的颜色起始位置”如果还记着4就漂了。这种漂移正是GapBuffer里所有标记管理的混乱之源。更糟的是标记不是只有光标的单个点。选区是一对点语法高亮是一堆区间断点、书签、折叠区、搜索结果命中全是区间。每次gap一动、文本一删所有这些偏移量在旧坐标系里的记录都瞬间失效。1.2 为什么不能每次暴力更新标记最常见也最省事的做法是每次insert或delete之后遍历容器里所有标记逐个判断编辑位置和标记位置的关系然后加delta或减delta。代码确实简单复杂度也好看每次编辑O(K)K是标记总数。但真实编辑器里K一点都不小。打开一份较大的日志文件语法高亮会产生几万个高亮区间如果还叠加了折叠状态、TODO高亮、搜索结果匹配K能到几万甚至几十万。以每帧输入都触发几十次编辑操作来说每次编辑都全量扫一遍几万个标记CPU时间全烧在无意义的遍历上。更关键的是标记更新通常不只是改个int你还要触发UI重绘、折叠判断、语法状态失效等回调。一次全量遍历会连累大量无辜标记跟着抖动。我在自己写的模拟场景里测过一个例子1.2M字符的文本8500个标记区间连续输入60个字符每次输入都全量更新标记累计耗时超过80ms这在渲染帧内就是肉眼可见的卡顿。但真正受一次插入影响的标记往往只有编辑点附近那一小撮。想办法抽出“受影响标记子集”而不是全量扫描是所有后续优化的出发点。2. 标记管理的第一性原理锚点、跟随方向与分裂2.1 mark里到底该存什么不要只存一个int很多刚上手的人标记对象会写成这样struct Mark { int32_t offset; uint32_t color; };只存一个offset。这在静态文本上没问题一旦文本编辑起来马上就会遇到“offset到底代表什么”的模糊地带。offset是字符偏移还是物理数组下标是在这个编辑轮次开始前的逻辑位置还是可以滞后更新的过期位置我的实践是标记内存储的一定是逻辑锚点也就是“用户视角的字符序号”不是物理数组下标。GapBuffer内部怎么挪动物理下标怎么变标记不关心。标记只关心它锚定的那个字符在文本流转过程中是否被移动、删除或跨越。其次是标记必须区分零宽点和区间。零宽点表示“夹在两个字符之间的位置”光标的插入点、选区起点都是零宽点区间则是一对锚点start和end各自记录一个位置。高亮、书签对cover的范围都是区间。再来是跟随方向。这个属性是标记管理真正复杂起来的地方。每个标记都要明确在“插入点和锚点重合”时自己跟着左边走还是跟着右边走。没有这条光标会在你从中间插入文本时跑到奇怪的一侧。我习惯的标记结构长这样enum class AnchorSide { Left, Right }; struct Mark { uint64_t id; int64_t pos; // 逻辑字符偏移可能比物理 index 小或大 AnchorSide side; // 重合时的跟随方向 bool zero_width; // 是否是零宽标记 uint32_t flags; // 折叠、语法、书签等用途标识 uint32_t offset_to_end; // 区间终点到起点的距离区间标记用 };区间标记的开销和普通点一样只需要一个起点和长度。维护区间时起点锚点的side和终点锚点的side可以不同这给了我们很灵活的控制。2.2 跟随方向怎么选插入、删除与边界重合的三种情况先看一个最经典的场景光标是一个零宽标记位置在第5个字符和第6个字符之间。用户按下字母文本在位置5处插入新字符x。那么x到底插在光标的左边还是右边直觉行为是光标应该从旧位置5变成新的位置6因为用户输入一个字符后光标要跑到字符x的后面等待继续输入下一个字符。这意味着插入点与锚点重合时光标插入标记选择向右跟随。反过来看书签。假设第5个字符是某个单词的开头书签锚在那里。在它前面插入一个x后用户通常希望书签仍然指向那个单词开头而不是滑到x后面。所以书签这类语义标记更适合Left跟随。删除场景更微妙。如果删除区间恰好把一个标记锚点覆盖了标记应该残留在删除区间的左侧边界还是右侧边界这个答案不能一概而论。光标在删除区间内时通常希望回到删除区间的起始位置也就是左侧边界。书签如果完全落进删除区间内选择消失也是在理但高亮区间如果首尾都在删除区间内这个区间就彻底没了你需要把对应UI状态也一并清掉。我们还可以用一段很小的代码来模拟分裂逻辑void apply_shift(Mark mark, int32_t edit_pos, int32_t delta) { if (edit_pos mark.pos) { // 编辑点完全在标记之前标记不受影响 return; } if (edit_pos mark.pos) { // 编辑点完全在标记之后如果delta为负可能跨越标记 return; } // edit_pos mark.pos此时看跟随方向 if (mark.side AnchorSide::Left) { // 标记留在原位置 return; } else { mark.pos delta; } }当然这只是一个最简版本。当delta为负也就是删除操作时还要考虑删除区间是否完全把标记涵盖。如果标记的pos落在删除区间内部但标记选择了Right跟随它就会锚定到删除区间的右边界。大部分时候这个语义是对的一个被删掉的高亮区间它的右端边界应该并到删除后的文本流里。2.3 区间跨过编辑点合并与保留的抉择区间标记比零宽点多一层复杂度start和end可能被同一次编辑分别命中。插入发生在区间内部时区间长度增大位置不变。插入发生在区间边界时start和end的side必须一起决定区间是否扩张。在折叠代码块的实现里我特别推荐一种组合区间的start用Left侧区间的end用Right侧。这样即使你在折叠区间的最前面或者最后面插入新文本语义上这个折叠块也不会意外吞掉新文本。比如你在一个代码块的闭合括号后面直接按回车插入新行如果end用了Left侧新行会跑到折叠块外部符合直觉如果end用了Right侧新行会被划进块内折叠起来时新行会消失很多插件的折叠bug就是这么来的。删除跨过区间中部时区间要“截断”start不动end向上收缩到删除区间的左边界同时考虑右边是否还有内容跟随。如果删除区间完全覆盖了start和end那么这个标记应该被销毁但要注意把“销毁”挂到事务回调里不能当场清内存原因后面讲undo时会提到。3. 高效更新的核心武器区间增量与延迟换算3.1 换一种思路让标记先“过期”查询时再修正暴力更新的实时性是“编辑发生后立刻修正所有标记”。区间增量方案的思路是反过来的反正一次性编辑只影响一个偏移区间为什么不把这些偏移记录在一个地方等真正需要读取某个标记位置时再临时把修正量加上我常用的一个比喻是与其每次图书馆搬完书都重贴一遍所有标签不如在门口贴一张“近期搬动记录”的公告读者找书的时候自己核对一下去向。GapBuffer是那本不断被搬动的书标记是标签公告栏则是一棵区间增量树。具体落地是这样的。每次insert、delete、replace完成后不直接对标记集合做全量遍历而是构造一个偏移事件offset、delta。如果delta是正数表示从offset开始其右侧所有逻辑位置都要向后平移如果是负数右侧位置都可能要前移。我们把这个事件送进一棵线段树中线段树的每片叶子代表文本中的一个原始逻辑位置节点保存着该区间横跨过的累计delta。实际读取一个标记位置时把它存储的过期pos拿去线段树中查询求出所有覆盖这个位置的delta累加值再与过期pos相加得到当前有效的位置。这种做法的核心好处有两个。第一每次编辑的增量维护成本从O(K)降到了O(log n)第二真实需要读取标记位置并不是每帧每个标记都读一遍只有光标移动、绘制可见行、状态计算时才读取延迟换算天然把CPU开销从编辑路径迁到了读取/绘制路径而读取路径是可以按需节流的。3.2 线段树维护累计增量的两种落地形态线段树的形态可以有两种。一种是直接对原始文本长度建立区间树叶子就是每一个字符槽。插入文本后需要把插入区间对应的叶节点数量扩大这个膨胀操作稍有点麻烦因为树在动态增长。另一种更稳的形态不直接以“物理字符”为叶子而是以“标记锚点所在的逻辑坐标空间”为索引。每棵树的叶子维护的是“从区间起点到当前位置的累计编辑增量”。新增的编辑事件会作用在一个半开区间[offset, offsetlen)上所有逻辑位置落在该区间之后的标记查询时都能累加到这个delta逻辑位置在区间内的标记则由分裂和跟随规则单独处理。我给出一种简化的伪代码形态便于理解class DeltaTree { vectorint32_t tree; // 朴素实现可用差分数组BIT生产环境用线段树 public: void add_shift(int32_t from, int32_t to, int32_t delta) { // 对区间 [from, to) 内所有位置记录一个 delta 偏移 range_add(from, to, delta); } int32_t query_shift(int32_t pos) { int32_t shift point_query(pos); return shift; } };查询耗时是O(log n)。如果只用一个差分数组加树状数组维护更多依赖“只增不减”的前提但GapBuffer里删除会让delta变成负数且会反复调整同一区间树状数组还是能胜任的注意初始化和版本管理就好。生产环境里我不会用vector直接做而是自定义一个内存占用可控的区间树每个节点除了delta还存子树的最大偏移量用于二分定位。实测在8500个标记的场景下查询一个标记位置的成本降到个位数纳秒级别完全不是瓶颈。3.3 到底划不划算一个复杂度对照表为了说服团队里坚持暴力更新的同事我整理过一张对照表。场景是1.2M字符、8500个区间标记连续输入60个字符每次输入都触发一次编辑回调方案每次编辑的平均额外成本60次输入累计耗时参考复杂度量级全量遍历并修正所有标记约8500次偏移计算大量UI回调实测约80msO(K)直接更新编辑点右侧所有标记平均约4250次偏移计算实测约38msO(K/2)线段树区间增量延迟查询1次范围add约O(log n)实测约3msO(log n)这个表虽然是我在本地模拟工程里测出来的数据不同语言、不同机器会有浮动但结论方向不会变当K上千、编辑频率高时区间增量方案是碾压级的。但这不代表暴力更新一无是处。如果标记数量少于100个每次编辑的遍历成本微不足道反而引入线段树、版本号、延迟刷新会让代码复杂得不成比例。我个人的决策线是这样的标记总数小于500时直接用数组存标记、每次编辑也不全量遍历只遍历一次通过排序好的标记区间快速筛出受影响子集超过500且编辑频率高再上区间增量方案。4. 落地一个可用的标记系统事务、索引与协作4.1 双索引结构按位置查找和按ID查找不能少一个实际的标记系统光有delta树还不够还要同时维护两个方向的索引。按位置排序的索引用来解决“给定一个文本位置有哪些标记覆盖它”这在语法高亮绘制时极其重要。在这个索引里所有区间标记按起点位置排序。我用了红黑树变体每个节点对应一个标记key是起点pos。这样找某个位置附近的所有标记只需要取low_bound后向后面取一段即可。按ID索引用来解决“UI操作拿到了一个标记句柄怎么快速拿到它的最新位置”。用户点击高亮控件、折叠三角形、断点管理器传递过来的是标记id。用一个哈希表维护id到指针的映射才可以避免每次通过position索引反向搜索。两个索引必须保持一致这对所有修改标记的操作都提出了统一入口的要求。我从来不直接暴露裸指针而是提供add_mark、remove_mark、move_mark三个API由它们去同步两棵索引结构。4.2 编辑事务批处理是标记稳定的生命线GapBuffer的插入删除可以独立调用但在标记管理的视角里它们必须按事务的方式组合起来。这不是过度设计而是被IME输入法、撤销重做、批量替换逼出来的。输入法打拼音时编辑器会收到一堆零散的insert和delete组合。如果每接收一个编辑事件就去同步标记、触发UI回调、刷新折叠状态你就会看到高亮区域在组词过程中疯狂闪烁而且性能极差。给编辑操作套一个事务以后一切就不一样了marker_transaction_begin(); gap_buffer-insert(edit.offset, edit.text, edit.len); gap_buffer-delete(edit.offset, edit.len); marker_transaction_commit();begin时记录每个标记的旧位置快照。commit时把所有编辑事件合并成一个大的delta事件一次性丢进DeltaTree里。中间标记全部保持旧位置查询时看不到中间态。commit后只对那些“真正被编辑跨越”的标记做分裂、合并或删除。这个机制是保证光标不闪烁、高亮不抖动的关键。这样做还会带来另一个好处撤销与重做变得可行。因为整个事务期间的所有编辑可以被压成一个逆deltaundo时只需要对DeltaTree执行反操作标记位置随之全部回退。4.3 别忘了GapBuffer自己的移动成本标记树做得再好GapBuffer如果频繁做远程gap移动memmove的流量依然会拖后腿。gap一次移动的距离越长复制的字节越多。所以我的经验是两个系统要一起优化。在连续输入的路径上gap本来就停在光标附近插入操作的成本很低。如果遇到“先删除一大段再在远离当前gap的位置插入”的场景gap移动是没办法避免的但可以通过批处理把多次移动重排为移动次数最少、每段移动距离最短的顺序。另一个隐藏很深的问题移动gap会改变tail段的物理位置但标记系统不感知物理地址只感知逻辑位置偏移。所以性能优化只管memmove就好标记系统不用跟着做对物理下标的修正。这也是把“逻辑锚点”和“物理下标”彻底解耦的好处之一。4.4 标记的创建、拆分、销毁与内存安全标记对象不能频繁new/delete否则会形成严重的内存碎片和缓存命中率下降。我用的是内存池加句柄化。所有Mark对象从池里分配id就是池里的索引。外部提到标记时只持有id绝不持有裸指针这样即使标记被销毁UI层拿到的id也只是一个“可能失效”的id不会悬空。跨事务期间如果某个标记被标记为“待销毁”我也不会立即从池里回收。我会先把它的id放进一个回收队列等当前事务提交、所有UI回调处理完之后才真正归还给池子。这个延迟回收机制避免了回调里还要判断对象是否还活着。拆分的场景多一些一个区间标记被插入事件刚好击穿如果它的start和end都落在编辑点两侧就需要把原区间拆成两个新区间分别锚定左右。这块逻辑很容易被漏掉漏掉的症状就是高亮区域在插入文本后多出半截污染色块。5. 高频翻车现场与排查技巧5.1 批量替换后光标飞到了奇怪的位置这个问题我调过不止一次。症状是执行一次全选替换后光标没有落在预期的新文末而是跳到了文档开头或者中间。多数原因是替换操作被做成了“先delete大区间再insert新区间”但中间隔着一次独立的标记同步。删除阶段原光标锚点被删除区间吞掉按跟随规则被归位到了删除区间的左边界插入阶段执行时又把这个光标当成了新区间的普通标记没有把它的位置重置到应有位置。正确做法是replace必须包在同一个事务里删除完成时不立刻解析标记归属而是记录一段“删除区间覆盖了哪些标记”等插入完成后对涉及的光标类标记统一重设锚点到新插入文本的期望端点。顺序不能乱。5.2 折叠区在编辑后头部或尾部多吞了一行折叠控件的区间start与end必须分开设置跟随方向。我推荐start用Left侧end用Right侧。这样折叠块就像一个“自己能稳住边界但不会吞新内容”的容器。常见的错误是所有标记统一用Right侧结果在折叠区间前插入一个新的空行时新空行被划进折叠块内折叠后看起来就是无缘无故少了一行展开后又看到空行挤在块内。一个排查技巧给每个标记加一个调试字段标注它是由哪个折叠语法定向生成的。发现边界错位时打印这个标记的side和pos基本能一眼定位是哪个环节没按规则走。5.3 撤销之后高亮区间和文本错开半个字符这是undo栈设计问题。只把文本的delta压栈却没有把标记的delta压栈撤销时文本回去了标记还停在新坐标上。我给每个事务增加一个可选的reverse事件队列队列里记录的是标记操作的反操作分裂的合并、合并的分裂、left与right的互换。commit时顺带生成reverse队列并压入undo栈undo时先应用文本delta再按逆序回放reverse队列。这样文本和标记始终保持同一步调。5.4 一个反直觉的优化结论最后说一个让我自己着实意外过的洞见。我第一次给标记系统上线段树时整体性能反而下降了。排查后发现问题出在“每次编辑后立即提交DeltaTree的range_add”上。虽然range_add本身是O(log n)但它伴随的对两个双索引的同步操作、对受影响标记的逐个检查依然是高频路径上的全量回调。后来把重心从“索引本身有多快”挪到了“能不能减少调用次数”上。批量事务和延迟提交一上整体帧时间立刻降了下来。换句话说高效标记管理的第一瓶颈往往不是数据结构而是更新策略。所以现在我做这类系统都会先从操作频率入手。高频操作尽量合并低频操作才允许直接遍历。真正把事务通道做好以后再回头修剪树结构性价比极其可观。个人在实际落地中的体会是GapBuffer的标记管理更像是一套围绕“锚点语义”的协调规则而不是某一个神奇的数据结构。把跟随方向、分裂规则、事务边界、延迟换算这几个点梳理清楚剩下的工作就是按序实现。如果你正在被编辑器的光标抖动、高亮漂移、折叠错位这些问题折磨建议先别急着换数据结构把这一套事务和锚点逻辑理一遍多半比之前任何方案都省心。
做编辑器内核这些年我发现一个特别有意思的现象很多人聊起GapBuffer都觉得它无非就是“一块数组开个口子插入删除少挪数据”原理简单到可以随手写出。可真把GapBuffer放进一个带语法高亮、代码折叠、书签、光标的完整编辑器里真正折磨人的从来不是gap本身而是围绕它长出来的一大堆标记——也就是Mark的维护问题。GapBuffer的高效写入能力和文本标记位置的正确性天生就是一对矛盾。文本一变所有记在旧位置上的标记全部作废。如果你靠“每次编辑后遍历所有标记逐个偏移”的笨办法能把一个输入法连续敲字的过程卡出掉帧动画。这篇文章我想聊聊我在这类标记管理上的完整思路锚点规则、区间增量树、批量事务通道以及那些踩过之后才明白的坑。内容适合正在写编辑器、IDE插件、日志高亮、富文本内核的开发者参考也适合对文本数据结构有兴趣、想理解“标记到底怎么跟文本一起走”的人。1. GapBuffer到底卡在哪一次插入引发的标记漂移1.1 从逻辑位置到物理偏移gap是怎么“背叛”标记的先快速过一遍GapBuffer的结构。它本质上一个内存块里开了个“空腔”空腔左边是已确认的文本head右边是tail。光标在哪个位置空腔就被挪到那个位置挪动方式是一次memmove把尾段数据平移。插入文本时写入空腔中删除文本时如果删除范围覆盖到空腔边缘就调整空腔的起点和终点。这套方案最大的好处是局部写入的代价极低尤其是连续输入时gap一直停在光标附近每次按键几乎只是往间隙里填字符。但问题在于文本的“逻辑位置”和它在数组里的“物理下标”之间隔着一层gap的距离。举个例子。假设缓冲区里有ABCDEF六个字符gap不在任何地方时A的物理下标是0、E的下标是4。如果我想在E之前插入xyz需要先把gap移动到E的位置。移动完的瞬间数组物理分布变成了AB CD 下划线区 xy 下划线区不对准确说是head是ABtail是CDEFgap就在B和C之间。E此刻的物理下标变成了5比原来的4偏了一位。标记“E字符的颜色起始位置”如果还记着4就漂了。这种漂移正是GapBuffer里所有标记管理的混乱之源。更糟的是标记不是只有光标的单个点。选区是一对点语法高亮是一堆区间断点、书签、折叠区、搜索结果命中全是区间。每次gap一动、文本一删所有这些偏移量在旧坐标系里的记录都瞬间失效。1.2 为什么不能每次暴力更新标记最常见也最省事的做法是每次insert或delete之后遍历容器里所有标记逐个判断编辑位置和标记位置的关系然后加delta或减delta。代码确实简单复杂度也好看每次编辑O(K)K是标记总数。但真实编辑器里K一点都不小。打开一份较大的日志文件语法高亮会产生几万个高亮区间如果还叠加了折叠状态、TODO高亮、搜索结果匹配K能到几万甚至几十万。以每帧输入都触发几十次编辑操作来说每次编辑都全量扫一遍几万个标记CPU时间全烧在无意义的遍历上。更关键的是标记更新通常不只是改个int你还要触发UI重绘、折叠判断、语法状态失效等回调。一次全量遍历会连累大量无辜标记跟着抖动。我在自己写的模拟场景里测过一个例子1.2M字符的文本8500个标记区间连续输入60个字符每次输入都全量更新标记累计耗时超过80ms这在渲染帧内就是肉眼可见的卡顿。但真正受一次插入影响的标记往往只有编辑点附近那一小撮。想办法抽出“受影响标记子集”而不是全量扫描是所有后续优化的出发点。2. 标记管理的第一性原理锚点、跟随方向与分裂2.1 mark里到底该存什么不要只存一个int很多刚上手的人标记对象会写成这样struct Mark { int32_t offset; uint32_t color; };只存一个offset。这在静态文本上没问题一旦文本编辑起来马上就会遇到“offset到底代表什么”的模糊地带。offset是字符偏移还是物理数组下标是在这个编辑轮次开始前的逻辑位置还是可以滞后更新的过期位置我的实践是标记内存储的一定是逻辑锚点也就是“用户视角的字符序号”不是物理数组下标。GapBuffer内部怎么挪动物理下标怎么变标记不关心。标记只关心它锚定的那个字符在文本流转过程中是否被移动、删除或跨越。其次是标记必须区分零宽点和区间。零宽点表示“夹在两个字符之间的位置”光标的插入点、选区起点都是零宽点区间则是一对锚点start和end各自记录一个位置。高亮、书签对cover的范围都是区间。再来是跟随方向。这个属性是标记管理真正复杂起来的地方。每个标记都要明确在“插入点和锚点重合”时自己跟着左边走还是跟着右边走。没有这条光标会在你从中间插入文本时跑到奇怪的一侧。我习惯的标记结构长这样enum class AnchorSide { Left, Right }; struct Mark { uint64_t id; int64_t pos; // 逻辑字符偏移可能比物理 index 小或大 AnchorSide side; // 重合时的跟随方向 bool zero_width; // 是否是零宽标记 uint32_t flags; // 折叠、语法、书签等用途标识 uint32_t offset_to_end; // 区间终点到起点的距离区间标记用 };区间标记的开销和普通点一样只需要一个起点和长度。维护区间时起点锚点的side和终点锚点的side可以不同这给了我们很灵活的控制。2.2 跟随方向怎么选插入、删除与边界重合的三种情况先看一个最经典的场景光标是一个零宽标记位置在第5个字符和第6个字符之间。用户按下字母文本在位置5处插入新字符x。那么x到底插在光标的左边还是右边直觉行为是光标应该从旧位置5变成新的位置6因为用户输入一个字符后光标要跑到字符x的后面等待继续输入下一个字符。这意味着插入点与锚点重合时光标插入标记选择向右跟随。反过来看书签。假设第5个字符是某个单词的开头书签锚在那里。在它前面插入一个x后用户通常希望书签仍然指向那个单词开头而不是滑到x后面。所以书签这类语义标记更适合Left跟随。删除场景更微妙。如果删除区间恰好把一个标记锚点覆盖了标记应该残留在删除区间的左侧边界还是右侧边界这个答案不能一概而论。光标在删除区间内时通常希望回到删除区间的起始位置也就是左侧边界。书签如果完全落进删除区间内选择消失也是在理但高亮区间如果首尾都在删除区间内这个区间就彻底没了你需要把对应UI状态也一并清掉。我们还可以用一段很小的代码来模拟分裂逻辑void apply_shift(Mark mark, int32_t edit_pos, int32_t delta) { if (edit_pos mark.pos) { // 编辑点完全在标记之前标记不受影响 return; } if (edit_pos mark.pos) { // 编辑点完全在标记之后如果delta为负可能跨越标记 return; } // edit_pos mark.pos此时看跟随方向 if (mark.side AnchorSide::Left) { // 标记留在原位置 return; } else { mark.pos delta; } }当然这只是一个最简版本。当delta为负也就是删除操作时还要考虑删除区间是否完全把标记涵盖。如果标记的pos落在删除区间内部但标记选择了Right跟随它就会锚定到删除区间的右边界。大部分时候这个语义是对的一个被删掉的高亮区间它的右端边界应该并到删除后的文本流里。2.3 区间跨过编辑点合并与保留的抉择区间标记比零宽点多一层复杂度start和end可能被同一次编辑分别命中。插入发生在区间内部时区间长度增大位置不变。插入发生在区间边界时start和end的side必须一起决定区间是否扩张。在折叠代码块的实现里我特别推荐一种组合区间的start用Left侧区间的end用Right侧。这样即使你在折叠区间的最前面或者最后面插入新文本语义上这个折叠块也不会意外吞掉新文本。比如你在一个代码块的闭合括号后面直接按回车插入新行如果end用了Left侧新行会跑到折叠块外部符合直觉如果end用了Right侧新行会被划进块内折叠起来时新行会消失很多插件的折叠bug就是这么来的。删除跨过区间中部时区间要“截断”start不动end向上收缩到删除区间的左边界同时考虑右边是否还有内容跟随。如果删除区间完全覆盖了start和end那么这个标记应该被销毁但要注意把“销毁”挂到事务回调里不能当场清内存原因后面讲undo时会提到。3. 高效更新的核心武器区间增量与延迟换算3.1 换一种思路让标记先“过期”查询时再修正暴力更新的实时性是“编辑发生后立刻修正所有标记”。区间增量方案的思路是反过来的反正一次性编辑只影响一个偏移区间为什么不把这些偏移记录在一个地方等真正需要读取某个标记位置时再临时把修正量加上我常用的一个比喻是与其每次图书馆搬完书都重贴一遍所有标签不如在门口贴一张“近期搬动记录”的公告读者找书的时候自己核对一下去向。GapBuffer是那本不断被搬动的书标记是标签公告栏则是一棵区间增量树。具体落地是这样的。每次insert、delete、replace完成后不直接对标记集合做全量遍历而是构造一个偏移事件offset、delta。如果delta是正数表示从offset开始其右侧所有逻辑位置都要向后平移如果是负数右侧位置都可能要前移。我们把这个事件送进一棵线段树中线段树的每片叶子代表文本中的一个原始逻辑位置节点保存着该区间横跨过的累计delta。实际读取一个标记位置时把它存储的过期pos拿去线段树中查询求出所有覆盖这个位置的delta累加值再与过期pos相加得到当前有效的位置。这种做法的核心好处有两个。第一每次编辑的增量维护成本从O(K)降到了O(log n)第二真实需要读取标记位置并不是每帧每个标记都读一遍只有光标移动、绘制可见行、状态计算时才读取延迟换算天然把CPU开销从编辑路径迁到了读取/绘制路径而读取路径是可以按需节流的。3.2 线段树维护累计增量的两种落地形态线段树的形态可以有两种。一种是直接对原始文本长度建立区间树叶子就是每一个字符槽。插入文本后需要把插入区间对应的叶节点数量扩大这个膨胀操作稍有点麻烦因为树在动态增长。另一种更稳的形态不直接以“物理字符”为叶子而是以“标记锚点所在的逻辑坐标空间”为索引。每棵树的叶子维护的是“从区间起点到当前位置的累计编辑增量”。新增的编辑事件会作用在一个半开区间[offset, offsetlen)上所有逻辑位置落在该区间之后的标记查询时都能累加到这个delta逻辑位置在区间内的标记则由分裂和跟随规则单独处理。我给出一种简化的伪代码形态便于理解class DeltaTree { vectorint32_t tree; // 朴素实现可用差分数组BIT生产环境用线段树 public: void add_shift(int32_t from, int32_t to, int32_t delta) { // 对区间 [from, to) 内所有位置记录一个 delta 偏移 range_add(from, to, delta); } int32_t query_shift(int32_t pos) { int32_t shift point_query(pos); return shift; } };查询耗时是O(log n)。如果只用一个差分数组加树状数组维护更多依赖“只增不减”的前提但GapBuffer里删除会让delta变成负数且会反复调整同一区间树状数组还是能胜任的注意初始化和版本管理就好。生产环境里我不会用vector直接做而是自定义一个内存占用可控的区间树每个节点除了delta还存子树的最大偏移量用于二分定位。实测在8500个标记的场景下查询一个标记位置的成本降到个位数纳秒级别完全不是瓶颈。3.3 到底划不划算一个复杂度对照表为了说服团队里坚持暴力更新的同事我整理过一张对照表。场景是1.2M字符、8500个区间标记连续输入60个字符每次输入都触发一次编辑回调方案每次编辑的平均额外成本60次输入累计耗时参考复杂度量级全量遍历并修正所有标记约8500次偏移计算大量UI回调实测约80msO(K)直接更新编辑点右侧所有标记平均约4250次偏移计算实测约38msO(K/2)线段树区间增量延迟查询1次范围add约O(log n)实测约3msO(log n)这个表虽然是我在本地模拟工程里测出来的数据不同语言、不同机器会有浮动但结论方向不会变当K上千、编辑频率高时区间增量方案是碾压级的。但这不代表暴力更新一无是处。如果标记数量少于100个每次编辑的遍历成本微不足道反而引入线段树、版本号、延迟刷新会让代码复杂得不成比例。我个人的决策线是这样的标记总数小于500时直接用数组存标记、每次编辑也不全量遍历只遍历一次通过排序好的标记区间快速筛出受影响子集超过500且编辑频率高再上区间增量方案。4. 落地一个可用的标记系统事务、索引与协作4.1 双索引结构按位置查找和按ID查找不能少一个实际的标记系统光有delta树还不够还要同时维护两个方向的索引。按位置排序的索引用来解决“给定一个文本位置有哪些标记覆盖它”这在语法高亮绘制时极其重要。在这个索引里所有区间标记按起点位置排序。我用了红黑树变体每个节点对应一个标记key是起点pos。这样找某个位置附近的所有标记只需要取low_bound后向后面取一段即可。按ID索引用来解决“UI操作拿到了一个标记句柄怎么快速拿到它的最新位置”。用户点击高亮控件、折叠三角形、断点管理器传递过来的是标记id。用一个哈希表维护id到指针的映射才可以避免每次通过position索引反向搜索。两个索引必须保持一致这对所有修改标记的操作都提出了统一入口的要求。我从来不直接暴露裸指针而是提供add_mark、remove_mark、move_mark三个API由它们去同步两棵索引结构。4.2 编辑事务批处理是标记稳定的生命线GapBuffer的插入删除可以独立调用但在标记管理的视角里它们必须按事务的方式组合起来。这不是过度设计而是被IME输入法、撤销重做、批量替换逼出来的。输入法打拼音时编辑器会收到一堆零散的insert和delete组合。如果每接收一个编辑事件就去同步标记、触发UI回调、刷新折叠状态你就会看到高亮区域在组词过程中疯狂闪烁而且性能极差。给编辑操作套一个事务以后一切就不一样了marker_transaction_begin(); gap_buffer-insert(edit.offset, edit.text, edit.len); gap_buffer-delete(edit.offset, edit.len); marker_transaction_commit();begin时记录每个标记的旧位置快照。commit时把所有编辑事件合并成一个大的delta事件一次性丢进DeltaTree里。中间标记全部保持旧位置查询时看不到中间态。commit后只对那些“真正被编辑跨越”的标记做分裂、合并或删除。这个机制是保证光标不闪烁、高亮不抖动的关键。这样做还会带来另一个好处撤销与重做变得可行。因为整个事务期间的所有编辑可以被压成一个逆deltaundo时只需要对DeltaTree执行反操作标记位置随之全部回退。4.3 别忘了GapBuffer自己的移动成本标记树做得再好GapBuffer如果频繁做远程gap移动memmove的流量依然会拖后腿。gap一次移动的距离越长复制的字节越多。所以我的经验是两个系统要一起优化。在连续输入的路径上gap本来就停在光标附近插入操作的成本很低。如果遇到“先删除一大段再在远离当前gap的位置插入”的场景gap移动是没办法避免的但可以通过批处理把多次移动重排为移动次数最少、每段移动距离最短的顺序。另一个隐藏很深的问题移动gap会改变tail段的物理位置但标记系统不感知物理地址只感知逻辑位置偏移。所以性能优化只管memmove就好标记系统不用跟着做对物理下标的修正。这也是把“逻辑锚点”和“物理下标”彻底解耦的好处之一。4.4 标记的创建、拆分、销毁与内存安全标记对象不能频繁new/delete否则会形成严重的内存碎片和缓存命中率下降。我用的是内存池加句柄化。所有Mark对象从池里分配id就是池里的索引。外部提到标记时只持有id绝不持有裸指针这样即使标记被销毁UI层拿到的id也只是一个“可能失效”的id不会悬空。跨事务期间如果某个标记被标记为“待销毁”我也不会立即从池里回收。我会先把它的id放进一个回收队列等当前事务提交、所有UI回调处理完之后才真正归还给池子。这个延迟回收机制避免了回调里还要判断对象是否还活着。拆分的场景多一些一个区间标记被插入事件刚好击穿如果它的start和end都落在编辑点两侧就需要把原区间拆成两个新区间分别锚定左右。这块逻辑很容易被漏掉漏掉的症状就是高亮区域在插入文本后多出半截污染色块。5. 高频翻车现场与排查技巧5.1 批量替换后光标飞到了奇怪的位置这个问题我调过不止一次。症状是执行一次全选替换后光标没有落在预期的新文末而是跳到了文档开头或者中间。多数原因是替换操作被做成了“先delete大区间再insert新区间”但中间隔着一次独立的标记同步。删除阶段原光标锚点被删除区间吞掉按跟随规则被归位到了删除区间的左边界插入阶段执行时又把这个光标当成了新区间的普通标记没有把它的位置重置到应有位置。正确做法是replace必须包在同一个事务里删除完成时不立刻解析标记归属而是记录一段“删除区间覆盖了哪些标记”等插入完成后对涉及的光标类标记统一重设锚点到新插入文本的期望端点。顺序不能乱。5.2 折叠区在编辑后头部或尾部多吞了一行折叠控件的区间start与end必须分开设置跟随方向。我推荐start用Left侧end用Right侧。这样折叠块就像一个“自己能稳住边界但不会吞新内容”的容器。常见的错误是所有标记统一用Right侧结果在折叠区间前插入一个新的空行时新空行被划进折叠块内折叠后看起来就是无缘无故少了一行展开后又看到空行挤在块内。一个排查技巧给每个标记加一个调试字段标注它是由哪个折叠语法定向生成的。发现边界错位时打印这个标记的side和pos基本能一眼定位是哪个环节没按规则走。5.3 撤销之后高亮区间和文本错开半个字符这是undo栈设计问题。只把文本的delta压栈却没有把标记的delta压栈撤销时文本回去了标记还停在新坐标上。我给每个事务增加一个可选的reverse事件队列队列里记录的是标记操作的反操作分裂的合并、合并的分裂、left与right的互换。commit时顺带生成reverse队列并压入undo栈undo时先应用文本delta再按逆序回放reverse队列。这样文本和标记始终保持同一步调。5.4 一个反直觉的优化结论最后说一个让我自己着实意外过的洞见。我第一次给标记系统上线段树时整体性能反而下降了。排查后发现问题出在“每次编辑后立即提交DeltaTree的range_add”上。虽然range_add本身是O(log n)但它伴随的对两个双索引的同步操作、对受影响标记的逐个检查依然是高频路径上的全量回调。后来把重心从“索引本身有多快”挪到了“能不能减少调用次数”上。批量事务和延迟提交一上整体帧时间立刻降了下来。换句话说高效标记管理的第一瓶颈往往不是数据结构而是更新策略。所以现在我做这类系统都会先从操作频率入手。高频操作尽量合并低频操作才允许直接遍历。真正把事务通道做好以后再回头修剪树结构性价比极其可观。个人在实际落地中的体会是GapBuffer的标记管理更像是一套围绕“锚点语义”的协调规则而不是某一个神奇的数据结构。把跟随方向、分裂规则、事务边界、延迟换算这几个点梳理清楚剩下的工作就是按序实现。如果你正在被编辑器的光标抖动、高亮漂移、折叠错位这些问题折磨建议先别急着换数据结构把这一套事务和锚点逻辑理一遍多半比之前任何方案都省心。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
