1 · neovim fold internal#

数据是如何保存的: 层级的动态数组garray_T

 typedef struct {
   linenr_T fd_top;      // first line of fold
   linenr_T fd_len;      // number of lines in fold
   garray_T fd_nested;   // array of nested folds
   char fd_flags;        // FD_OPEN, FD_CLOSED, or FD_LEVEL
   TriState fd_small;    // kTrue/kFalse/kNone for 'foldminlines'
 } fold_T;

增删改查:

1.1 · f_foldlevel :: 搜索#

可以看作在B树中的搜索

先看 foldlevel 函数的实现，其获取指定行的fold的级别

1. 先判断是否超过行范围
2. 调用foldLevel函数
3. 调用foldLevelWin函数，传入全局变量curwin(表示当前活跃窗口)和lnum

curwin 是 window_S 结构体，定义在 src/nvim/buffer_defs.h:1071

folds 通过 w_folds 字段保存，其是一个 garray_T 结构题，定义在 src/nvim/garray_defs.h:14 garray_T 的 ga_data 指向结构题fold_T，就是fold的数据，其fd_nested字段也是 garray_T 类型 定义在 src/nvim/fold.c:75

通过递归去调用foldFind，查找哪个fold包含了lnum，定义src/nvim/fold.c:1056

garray_T 是一个自增长的数组，有指向第一个元素的数据指针，有长度，有底层长度，有元素长度

元素长度？这个就要看foldFind的实现了，其会获取fold，那肯定知道 garray_T 数据是如何布局的

const garray_T *gap

// 1. 先判断长度，为0则直接返回
gap->ga_len == 0

// 2. 将数据指针，转换成 fold_T 类型
// NOTE: fp 指向的是一个数组，有多个fold_T
fold_T *fp = (fold_T *)gap->ga_data;

// 3. 执行一个二分搜索
linenr_T low = 0;
linenr_T high = gap->ga_len - 1;
while (low <= high) {
    linenr_T i = (low + high) / 2;
    // ...
    // 1. 如果fold开始行大于lnum，可能在前面的fold中
    // 缩小到前一半
    fp[i].fd_top > lnum
    high = i - 1;
    // ...
    // 2. 如果fold开始行+fold的长度，小于或等于lnum，可能在后面的fold中
    fp[i].fd_top + fp[i].fd_len <= lnum
    // 缩小到后一半
    low = i + 1;
    // 3. 否则就在当前fold中，直接返回
    *fpp = fp + i;
    return true;
}
// 4. 如果二分搜索结束后，还没有找到
// 这时候 low 是大于 high 的，直接返回
return false;

可知 foldFind 将包含当前 lnum 的fold 保存在了 fp 里 我们需要遍历 fp 的子fold，看哪个子fold包含了lnum 我们再看一下 foldLevelWin 函数

// NOTE: fd_nested 字段是garray_T类型，保存着子fold
fold_T *fp;


linenr_T lnum_rel = lnum;
// NOTE: 每次找到包含的fold，就加1，然后遍历子fold，递归直到不满足条件了
int level = 0;

garray_T *gap = &wp->w_folds;
while (true) {
    // 找fold是否包含lnum
    if (!foldFind(gap, lnum_rel, &fp)) {
      break;
    }
    // 找到了，那继续子fold吧
    gap = &fp->fd_nested;
    // NOTE: 对于子fold，fd_top是相对父fold的偏移
    // 所以减去偏移，才是fold真实的开始行
    lnum_rel -= fp->fd_top;
    // 既然找到了，那说名在更深的地方了，级别加1
    level++;
}

1.2 · foldCreate :: 增加#

:fold 命令创建fold

// 1. 获取范围
  pos_T start_rel = start;
  pos_T end_rel = end;

// 2. 如果是 marker 方式，则创建 marker
// 忽略

// 3. 找到插入的位置i，在gap数组中，也就是父fold
garray_T *gap = &wp->w_folds;
int i;
// 3.1 空fold的情况
// 3.2 查找包含开始行的fold
foldFind(gap, start_rel.lnum, &fp)
// 判断 fold 是包含目标范围的
fp->fd_top + fp->fd_len > end_rel.lnum

// 4. 新创建一个 fold 数组
garray_T fold_ga;
ga_init(&fold_ga, (int)sizeof(fold_T), 10);
// TODO src/nvim/fold.c:608

2 · neovim marktree internal#

src/nvim/marktree.c

tree -> 树形数据结构； 那mark是什么？任意数据？ 增删改查的操作都基于遍历算法：前序遍历、中序遍历、后序遍历

树形结构：插入节点？删除节点？修改节点？查找节点？

gravity: 方向性、优先级

tree -> node -> n个key(pos)

typedef struct {
  MTNode *root;
  // ...
} MarkTree;

typedef struct mtnode_s MTNode;

struct mtnode_s {
  MTNode *parent;
  struct mtnode_inner_s s[];
};

struct mtnode_inner_s {
  MTNode *i_ptr[2 * MT_BRANCH_FACTOR];
}

2.1 · 查找： marktree_lookup#

读取/删除操作：通过iter marktree_itr_get: 将iter放在指定的位置 marktree_itr_current: iter当前位置 marktree_itr_next/prev: iter前后位置

// 位置
typedef struct {
  int32_t row;
  int32_t col;
} MTPos;
#define MTPos(r, c) ((MTPos){ .row = (r), .col = (c) })

// marktree_itr_get -> marktree_itr_get_ext
bool marktree_itr_get_ext(MarkTree *b, MTPos p, MarkTreeIter *itr, bool last, bool gravity,
                          MTPos *oldbase, MetaFilter meta_filter)
{
  // 设置迭代器，如果有旧位置，使用旧位置
  itr->pos = (MTPos){ 0, 0 };
  itr->x = b->root; // 根节点
  itr->lvl = 0;
  if (oldbase) {
    oldbase[itr->lvl] = itr->pos;
  }
  // 开始迭代: 深度优先
  while (true) {
    // marktree_getp_aux: 当位置k存在与节点itr-x时，返回其索引；否则返回其应该插入的位置
    itr->i = marktree_getp_aux(itr->x, k, 0) + 1;
    // 当前节点level为0则跳出循环
    if (itr->x->level == 0) {
      break;
    }
    // 修改当前迭代器节点
    itr->x = itr->x->ptr[itr->i];
  }
  // ??
  return marktree_itr_prev(b, itr);
}

marktree_lookup: 根据ID找

// itr 是可选的
MTKey marktree_lookup(MarkTree *b, uint64_t id, MarkTreeIter *itr)
{
  // 根据ID找到节点；节点包含多个MTKey，需要再查找
  MTNode *n = id2node(b, id);

  int i = 0;
  // 遍历
  for (i = 0; i < n->n; i++) {
    // 遍历节点含有的多个MTKey，找到符合的ID
    if (mt_lookup_key(n->key[i]) == id) {
      return marktree_itr_set_node(b, itr, n, i);
    }
  }
}

MTKey??

2.2 · 插入：marktree_put#

void marktree_put(MarkTree *b, MTKey key, int end_row, int end_col, bool end_right)
{
  // 把key放入树b
  marktree_put_key(b, key);
}

// src/nvim/extmark.c
// extmark_set -> marktree_put
// nvim_buf_set_extmark -> extmark_set
// buf_set_sign -> extmark_set
// 主要看看 buf_set_sign??

2.3 · 删除: marktree_del_itr#

marktree_del_itr

marktree_splice?

marktree_del_itr: 删除迭代器的当前mark且隐式前移

3 · neovim undo internal#

数据是树性结构？

如何增删改查

3.1 · f_undotree :: 返回当前buffer的undo树数据#

// 1. 返回值是一个字典，所以先分配内存空间

// 2. 参数是buf，空值时，使用当前buf

// 3. NOTE: 往返回的字典里塞数据，数据关联在当前buf上，类型 file_buffer
// 3.1 含一些undo树的状态信息：当前的节点
// 3.2 还一个列表，保存undo树的其他节点
// src/nvim/buffer_defs.h
typedef struct file_buffer buf_T;
struct file_buffer {
  // NOTE: 主要关注这些字段
  u_header_T *b_u_oldhead;     // pointer to oldest header
  u_header_T *b_u_newhead;     // pointer to newest header; may not be valid
                               // if b_u_curhead is not NULL
  u_header_T *b_u_curhead;     // pointer to current header


  // undo数据库是一个列表，持续加入中
  // 如果为true，表示已经加入到undo树了？
  bool b_u_synced;             // entry lists are synced
};

// 4. NOTE: 主要的数据结构:
// src/nvim/undo_defs.h
typedef struct u_header u_header_T;
struct u_header {
  // NOTE: 主要关注这些字段
  union {
    u_header_T *ptr;              ///< pointer to next undo header in list
    int seq;
  } uh_next;
  union {
    u_header_T *ptr;              ///< pointer to previous header in list
    int seq;
  } uh_prev;
  union {
    u_header_T *ptr;              ///< pointer to next header for alt. redo
    int seq;
  } uh_alt_next;
  union {
    u_header_T *ptr;              ///< pointer to previous header for alt. redo
    int seq;
  } uh_alt_prev;

  // entry 表示undo数据块，先忽略
  u_entry_T *uh_entry;            ///< pointer to first entry
};

// TODO: 具体 undo 数据块
typedef struct u_entry u_entry_T;
struct u_entry {};

1. 3个head指针： b_u_oldhead 指向树根节点 b_u_newhead 指向最新的节点（最近修改） b_u_curhead 指向当前节点 (undo N 命令)

2. u_header 类型：代表undo树上的节点 uh_next, uh_prev 分别指向前后节点，双链表 uh_alt_next, uh_alt_prev 表示分支：双链表上的节点，共用一份entry数据 ？

3.1.1 · 来几个操作看一下

1. 插入节点
2. 回退节点
3. 插入节点：产生新分支
4. 跳到任意节点：

跳到任意节点，应该是个遍历，先看一下如何遍历的：对应 :undo 命令

// src/nvim/ex_docmd.c
static void ex_undo(exarg_T *eap)
{
      u_undo(1);                    // :undo
}

// src/nvim/undo.c
void u_undo(int count)
{
    u_doit(count, false, true);
}
static void u_doit(int startcount, bool quiet, bool do_buf_event)
{
  int count = startcount;
  // NOTE: 逐步回退到某个点：可以理解为叶子节点，向上逐步回到某个祖宗节点
  while (count--) {
    if (undo_undoes) {} else {
      // 执行文本变更，先忽略
      u_undoredo(false, do_buf_event);
      // NOTE: uh_prev 前一个节点，重设当前节点
      curbuf->b_u_curhead = curbuf->b_u_curhead->uh_prev.ptr;
    }
  }
}

回退节点就是跳到任意节点的一个变体：跳回最近一个节点

ok，现在来看一下插入，可能有产生新分支的情况，通过当前节点的uh_next来判断，如果有说明需要产生新分支？

// src/nvim/undo.c
// 保存 top 到 bot 之间的修改
int u_save(linenr_T top, linenr_T bot)
{
  return u_save_buf(curbuf, top, bot);
}
int u_save_buf(buf_T *buf, linenr_T top, linenr_T bot)
{
  return u_savecommon(buf, top, bot, 0, false);
}
int u_savecommon(buf_T *buf, linenr_T top, linenr_T bot, linenr_T newbot, bool reload)
{
  if (buf->b_u_synced) {
    // 创建一个新节点
    u_header_T *uhp;

    // 保存当前节点
    u_header_T *old_curhead = buf->b_u_curhead;

    // 原节点之前插入新节点: 产生新分支？
    // 处理 uh_alt_next/uh_alt_prev
    uhp->uh_alt_next.ptr = old_curhead;
    uhp->uh_alt_prev.ptr = old_curhead->uh_alt_prev.ptr;
    uhp->uh_alt_prev.ptr->uh_alt_next.ptr = uhp;
    old_curhead->uh_alt_prev.ptr = uhp;
    // uh_prev/uh_next
    // 原节点之后插入新节点
    // FIX: 插入操作似乎不完全？
    buf->b_u_newhead = old_curhead->uh_next.ptr; // 暂存原节点下一节点
    uhp->uh_prev.ptr = NULL;
    uhp->uh_next.ptr = buf->b_u_newhead; // 新节点下一节点指向原节点下一节点
    buf->b_u_newhead->uh_prev.ptr = uhp; // 新节点下一节点的前节点，指向当前节点
    buf->b_u_newhead = uhp;

    // 处理序列号加
    uhp->uh_seq = ++buf->b_u_seq_last; 
    buf->b_u_seq_cur = uhp->uh_seq;
    // undo块数据，先忽略
    uhp->uh_entry = NULL;
    // 设置为最新节点
    buf->b_u_newhead = uhp; 

  }
}