Skip to content

Design.md

Latest commit

 

History

History
361 lines (252 loc) · 37 KB

Design.md

File metadata and controls

361 lines (252 loc) · 37 KB
Raw

substate 设计

本文档规定 substate 的结构：所有权模型、节点与动作、事务、通知、ID，以及为预写式日志（WAL）预留的接口。第一阶段的历史记录只保存在内存中，本文档规定的接口在实现 WAL 时无需修改，见「实施阶段」。

概要

文档是一棵节点树。树的所有修改都在事务中进行，每个修改记录为一个动作，一个事务构成一个撤销步骤。每个节点在任何时刻都只有一个所有者：用户、父节点、模型的根槽位，或历史记录中的一个动作。 被删除的节点不再以「已废弃」状态留在树中，而是由删除它的动作持有。

设计依据

substate 的早期实现（e403859）同时以 std::shared_ptr、可切换持有与借用的 SmartPtr 和裸指针三种方式表示节点的所有权，另有 8 项行为缺陷。AceTreeModel 的「已废弃」状态以插入节点的事件负责释放节点，在淘汰历史时可能释放仍被后续删除事件引用的节点。细节见 References.md，本文档的设计以其结论为依据。

设计目标

  1. 所有权可从类型确定。 只使用 std::unique_ptr 与非持有的裸指针，不使用 std::shared_ptr，不使用运行时切换角色的指针。
  2. 撤销与重做精确还原，包括节点身份：撤销删除后恢复的是同一个对象，其地址与 ID 均不变。
  3. 事务具有原子性：中止事务后，树与事务开始前完全相同。
  4. 通知完整：执行、撤销、重做均发出通知，并给出实际发生的变化。
  5. 为 WAL 预留完整接口：实现 WAL 时只新增存储引擎，不修改节点、动作与模型的公开接口。
  6. 核心库不依赖 Qt。

非目标

  • 第一阶段不实现 WAL、检查点、异步写入和历史记录的换出。
  • 不支持多线程访问。模型及其节点只在一个线程中使用。
  • 不支持事务嵌套。需要嵌套的调用方（如 HelloUTAU 的领域函数）在自身一层计数。
  • 不支持协同编辑与分支合并。

所有权模型

规则：每个节点在任何时刻都恰好有一个所有者。

所有者 节点状态 持有方式
用户 未进入模型，称为自由节点 调用方的 std::unique_ptr<Node>
父节点 在树中 父节点容器中的 std::unique_ptr<Node>
模型 树的根 Model 的根槽位
动作 在历史记录中，不在树中 动作中的 std::unique_ptr<Node>

所有权随动作转移，节点对象本身从不移动或复制：

操作 执行 撤销
插入 节点从调用方转入父节点，动作不持有节点 节点从父节点转入动作
删除 节点从父节点转入动作 节点从动作转回父节点
替换槽位中的子节点 旧节点转入动作，新节点转入父节点 相反
替换根节点 旧根转入动作，新根转入模型 相反
转移 节点从源父节点直接转入目标父节点，动作不持有节点 节点从目标父节点转回源父节点

由此得出：

  • 不再需要 Detached 状态。 节点是否在树中由「是否挂在树上」决定，以 isAttached() 表示。节点进入或离开树时，模型沿子树传播该标志，其代价与插入删除本身同阶。
  • 节点真正析构的时机只有三种：持有它的动作被丢弃（提交新事务时截断重做分支，或历史记录超出上限时淘汰最早的步骤）、模型重置、自由节点被调用方释放。
  • 动作所引用的节点在该动作存在期间始终存活，被删除的节点都有所有者。 所依赖的约束与证明见「所有权的正确性」。
  • Property 成为只可移动的类型，因为它可能持有子节点。复制子树须显式调用 clone()。

调用方对节点的引用

  • 裸指针 Node * 在节点析构前有效。 节点被删除后，指针在该删除被撤销、重做期间一直有效，直到持有它的动作被丢弃。
  • 需要长期保存的引用使用 ID，通过 Model::nodeById() 取回，节点析构后返回空指针。界面中的选区、拖动中的对象均应保存 ID。
  • 模型在节点析构前发出通知，供持有裸指针的调用方清理。

自由节点

自由节点可以任意修改，不产生动作，不需要事务。从自由节点上移除的子节点返回给调用方（take 系列函数），而非就地销毁。一个节点一旦进入模型，就不能再挂到其他模型上，除非先由调用方以 clone() 复制。在同一模型内更换父节点须使用转移，见「动作」中的「转移」。

所有权的正确性

本节列出所有权模型所依赖的约束，并证明在这些约束下，References.md 所述 AceTreeModel 的两个问题不会出现：被引用的节点被提前释放，以及被删除的节点永不释放。证明包含转移动作，即节点在保持身份的前提下更换父节点，见「动作」中的「转移」。

记号

  • 历史记录中的事务依次记为 T(1)、T(2) 等。引擎保留 T(m+1) 至 T(n)，当前步数为 c，m ≤ c ≤ n。T(1) 至 T(c) 为已执行的事务，T(c+1) 至 T(n) 为未执行的事务，即已撤销、可重做的事务。代码中二者对应 Action::State 的 Applied 与 Unapplied，表示动作的变化当前是否体现在树上。
  • 全部动作按执行位置排成全序：先比较所属事务的编号，同一事务内按执行顺序。a < b 表示 a 位于 b 之前。任何时刻，已执行的动作构成这一全序的一个前缀。
  • 位置指全序中两个相邻动作之间的间隔。C(π) 为执行位置 π 之前的全部动作后得到的树，称为位置 π 上的构型。从 T(m) 结束处到 T(n) 结束处的位置称为保留的位置。当前位置是 T(c) 结束处，或者进行中的事务里最后一个动作之后。进行中的事务视为保留的事务。
  • 对一个进入过模型的节点 x，ins(x) 为把 x 挂到父节点上的动作，rem(x) 为把 x 从父节点上取下的动作。不存在时，ins(x) 视为位于全序之前，rem(x) 视为位于全序之后。替换槽位中子节点的动作，对旧节点是 rem，对新节点是 ins。转移动作既不是 ins 也不是 rem。
  • 「x 有父节点」指 x 挂在某个节点上，或位于模型的根槽位。x 在树中，当且仅当 x 及其全部祖先都有父节点。

约束

  1. 单一入口。 节点只能以自由节点的身份进入模型。进入模型后，调用方无法再取得它的所有权：删除操作不返回被删除的节点，被删除的节点只能经撤销回到删除前的父节点上。
  2. 持有规则。 插入动作在未执行时持有其插入的节点，删除动作在已执行时持有其删除的节点。除此之外，动作不持有节点。转移动作在任何时刻都不持有节点。
  3. 丢弃规则。 引擎只以两种方式丢弃事务。淘汰按从旧到新的顺序丢弃最早的已执行事务。截断丢弃全部未执行事务。中止事务等价于执行其全部动作、撤销、再截断。
  4. 析构不访问引用。 动作的析构函数不访问它引用而不持有的节点。因此同一事务内的动作可以按任意顺序析构。
  5. 只修改树中的节点。 动作只作用于在树中的节点：插入、删除、赋值与移动的父节点在树中，转移的源父节点与目标父节点也都在树中。
  6. 父子关系的变化。 只有插入、删除、转移及其撤销改变父子关系。移动只在同一父节点内重排子节点。转移使节点从一个父节点直接挂到另一个父节点上，节点在转移前后都有父节点。目标父节点不能是被转移节点本身或其后代，否则会形成环。

引理 1：每个节点至多被挂上一次、取下一次

由约束 1，x 只能在自由时被挂上。被取下后，x 由删除动作持有（约束 2），调用方无法再次把它挂上。撤销与重做只按相反或原来的方向执行已有的动作，不产生新的动作。转移不使节点离开或进入模型。因此在任一时刻的历史记录中，ins(x) 与 rem(x) 各至多一个，且 ins(x) < rem(x)。初始树中的节点，即模型的初始根节点及其后代，以及恢复时由引擎构造的树中的节点，没有 ins(x)。

引理 2：父节点的判定

x 有父节点，当且仅当 ins(x) 已执行且 rem(x) 未执行。

证明：由约束 6，转移改变 x 的父节点，但不改变 x 是否有父节点。此外只有 ins(x)、rem(x) 及其撤销改变 x 是否有父节点。已执行的动作构成全序的前缀，且由引理 1，ins(x) < rem(x)，因此 x 有父节点恰在该前缀包含 ins(x) 而不包含 rem(x) 时。∎

引理 3：沿历史移动时构型逐一重现

从当前位置 ρ 到保留的位置 π，经撤销或重做依次经过二者之间的每一个位置，并在每个位置上得到该位置的构型。

证明：执行与撤销互为逆操作，并且每个动作被撤销时，树恰为它执行后的构型。归纳即得。∎

由引理 3 与约束 5，每个动作无论是执行还是撤销，其所作用的父节点都在当时的树中。

定理 1：所有者唯一

每个存活的、进入过模型的节点恰有一个所有者。

证明：若 x 有父节点，其父节点或根槽位持有 x。由引理 2，此时 ins(x) 已执行、rem(x) 未执行，按约束 2 二者均不持有 x，转移动作与其他动作也不持有 x。若 x 没有父节点，由引理 2，ins(x) 未执行，或 rem(x) 已执行。二者不会同时成立，因为 ins(x) < rem(x)，而已执行的动作构成前缀：ins(x) 未执行时 rem(x) 也未执行。因此恰有一个动作持有 x。∎

定理 2：可到达的节点存活

设 π 为保留的位置，y 在构型 C(π) 中。则 y 存活，并且 y 或者在当前的树中，或者位于一棵已取下的子树中，该子树的根由一个保留的事务中的动作持有。

证明：由引理 3，从 π 沿历史到当前位置 ρ，依次经过二者之间的每个构型，路径上的每个动作都属于保留的事务。若 y 在路径上始终在树中，则 y 在当前的树中。否则考虑 y 第一次离开树的那一步。节点离开树只有两种方式：执行某个 rem(q)，或撤销某个 ins(q)，其中 q 是 y 或 y 当时的祖先。转移不使任何节点离开树（约束 6）。这一步的动作 b 此后持有 q（约束 2），b 位于路径上，因此属于保留的事务。此后路径上的每一步只作用于树中的节点（引理 3 与约束 5），因此不修改以 q 为根的子树，y 也不会被转移出该子树。q 也不会被重新挂上，因为路径单调，b 不会被再次执行或撤销，而由引理 1，q 没有其他 ins 或 rem 可以把它挂回。因此到达 ρ 时，y 仍在由 b 持有的子树中，而 b 未被丢弃，y 存活。∎

推论（被引用的节点存活）。 设动作 a 属于保留的事务，p 为 a 所引用的任一父节点，包括转移的源父节点与目标父节点。则 p 存活。

证明：a 执行前的位置是保留的位置，由约束 5，p 在该位置的构型中，由定理 2 即得。∎

定理 3：没有无主的节点

没有父节点的模型节点，其所有者是历史记录中的一个动作，因此它最迟在该动作所在的事务被丢弃时析构。历史记录的长度有上限，所以不再可能回到树中的节点所占用的内存有上限。

证明：由定理 1 直接得出。∎

定理 4：析构的节点不会再出现

事务被丢弃时析构的节点，不在丢弃之后任何保留的位置的构型中，也不会出现在此后新提交的事务所产生的任何树中。

证明：设节点 x 随事务 D 的丢弃而析构，则 x 位于一棵已取下的子树中，其根的所有者属于 D。

  • 若 x 在丢弃之后某个保留的位置 π 的构型中，则 π 在丢弃之前也是保留的位置，且从 π 到当前位置的路径不经过 D 中的动作：淘汰只丢弃当前位置之前、最早的若干事务，截断只丢弃当前位置之后的全部事务。由定理 2，x 所在子树的根由路径上的一个动作持有，与定理 1 的唯一性矛盾。
  • 新提交的事务只作用于树中的节点（约束 5），不能挂上已取下的节点（约束 1），也不能把节点转移出已取下的子树。∎

与 AceTreeModel 的对照

  • 提前释放。 AceTreeModel 中，已取下节点的所有者是 ins(x)，即使 ins(x) 已执行。淘汰已执行的 ins(x) 时释放 x，而 x 在 rem(x) 执行之前的构型中，rem(x) 仍在历史记录中，违反定理 2 的推论。定理 2 的证明在此处失效，是因为使 x 离开树的动作是 rem(x)，而 AceTreeModel 中持有 x 的不是它。本设计中已执行的插入动作不持有节点，淘汰它不会析构任何节点。
  • 永不释放。 初始树中的节点没有 ins(x)，被取下后在 AceTreeModel 中没有所有者，违反定理 1。本设计中其所有者为 rem(x)，随 rem(x) 所在的事务被淘汰而析构。

可执行的检验

上述定理由测试检验，而不只依靠代码审查：

  • 随机测试的每一步之后，比较存活的模型节点集合与参照实现给出的集合，即当前的树中的节点，加上保留的事务中按约束 2 被持有的节点及其后代。二者相等，即同时检验定理 1 至 4。随机生成的动作包括插入、删除、替换、移动与转移。存活节点由计数的测试节点类型统计。
  • ID 索引中的条目数始终等于存活的模型节点数，重置和析构模型之后为零。该断言不依赖泄漏检测工具，Windows 上 MSVC 的 AddressSanitizer 不提供泄漏检测。
  • 长历史测试：提交的事务数为淘汰阈值的数倍，其中包含插入、删除、替换、根节点替换与转移，随后撤销到底、重做到顶。AceTreeModel 的两个问题都需要 200 次以上的提交才会出现。
  • References.md 中 AceTreeModel 的两个探针改写为测试，分别为在长历史中插入、删除、淘汰后撤销，以及删除初始树中的节点后淘汰。另加一项：把节点转移到另一个父节点，删除原父节点，淘汰删除之前的全部步骤后撤销，被转移的节点与原父节点都须存活且正确还原。
  • 转移的环检查：把节点转移到其自身或其后代之下须被拒绝。
  • 持久化的检验：随机历史中的每个动作在首次执行时写出，第二个模型从写出的初始树开始，只凭解码的动作重放，每一步两棵树连同 ID 与键都须相同，撤销与重做之后同样如此。此外定期从检查点（树与已执行动作持有的节点）和保留事务的编码恢复出第三个模型，各动作按其当前状态解码，恢复后池须为空，第三个模型随原模型撤销到最早、重做到最新，每一步都须相同。
  • 通知的检验：随机测试中注册一个只凭通知重建树的观察者，每一步比较重建的树与模型的树，并比较其记录的存活节点集合与参照实现给出的集合。二者相等，即检验了通知的完整性、方向，以及每个析构的节点都被通知。
  • 全部测试在 AddressSanitizer 下运行。

析构顺序

模型重置与析构按以下顺序进行：

  1. 发出 aboutToReset，此后不再发出逐节点的通知。
  2. 析构存储引擎，连同历史记录中各动作持有的节点。由约束 4，动作析构时不访问树中的节点，因此先后顺序不影响内存安全。规定引擎在前，是因为第二阶段的日志引擎在析构时可能需要写出检查点，此时树须仍然存活。
  3. 析构树。
  4. 最后析构 ID 索引。节点析构时从索引中移除自己，因此索引的生存期须覆盖全部节点。在 Model 中，索引成员声明于树与引擎之前。逐个移除的代价与节点数成正比，重置时可以接受。

节点类型

类型 所在库 内容 寻址
VectorNode substate 有序子节点 下标
SheetNode substate 子节点，按自增键索引，已删除的键不复用 键
BytesNode substate 连续字节 字节偏移
StructNode<N> qsubstate 固定数量的槽位，每个槽位为一个 Property 下标
MappingNode qsubstate 字符串到 Property 的映射 键

Property 为三种状态之一：空、一个 QVariant 标量、一个子节点。StructNode 与 MappingNode 依赖 QVariant，因此位于 qsubstate。

类型化数组

BytesNode 按字节存储与记录。存储元素数组（如音高曲线）时，由模板 ArrayNode<T> 在其上提供按元素下标的接口，要求 T 为可平凡复制的类型，偏移换算为「元素下标 × sizeof(T)」。存储、动作与序列化仍按字节进行，因此不引入新的动作类型。元素以本机字节序存储并原样写出，数值同样以本机字节序写出，因此 substate 只支持小端平台，在大端平台上编译时报错。目标平台 x86-64 与 ARM64 均为小端。

ArrayNode<T> 与 StructNode<N> 的默认类型分别为 Bytes 与 Struct，但类型不能确定 T 或 N，编解码器无法据此创建对象。参与序列化的 ArrayNode<T> 与 StructNode<N> 须使用用户类型并注册，见「用户节点类型」。

节点与数组的选择。 元素需要身份时，即被界面单独选中或拖动、被 ID 引用时，使用节点。数量大、定长、只作为数值序列整体编辑的元素，使用 ArrayNode<T>。例如 Mode2 音高的控制点须能单独拖动，使用 VectorNode。Mode1 音高曲线每 5 tick 一个值，使用 ArrayNode<T>。二者的代价相差一个数量级：以 MSVC 14.44 与 Qt 6.11.1 实测，由 std::monostate、QVariant 与 std::unique_ptr 组成的 std::variant，即 Property 的布局，为 40 字节，因此一个只含 3 个标量的 StructNode<3> 需要一个节点头、120 字节的槽位和一次堆分配，而同样的数据在数组中占 24 字节。

用户节点类型

Node::Type 从 User 起为用户类型。用户类型参与序列化，须以一个创建空的自由节点的工厂向 Codec 注册，见「持久化接口」。节点内容由节点自身的 writeContent() 与 readContent() 读写，因此继承 VectorNode 等类型而不增加内容的用户类型只需注册工厂。

动作

动作 记录内容 持有的节点
RootChange 新旧根 当前不在树中的一个
VectorInsert / VectorRemove 父节点、下标、数量 当前不在树中的子节点
VectorMove 父节点、下标、数量、目标位置 无
SheetInsert / SheetRemove 父节点、键 当前不在树中的子节点
BytesInsert / BytesRemove 父节点、偏移、字节 无
BytesReplace 父节点、偏移、新旧字节 无
Transfer 源父节点与位置、目标父节点与位置、被转移节点的 ID 无
StructAssign 父节点、槽位下标、新旧值 当前不在树中的子节点
MappingAssign 父节点、键、新旧值（均可为空） 当前不在树中的子节点
  • BytesReplace 不改变长度。 新旧字节长度相同。改变长度的替换由调用方组合删除与插入完成，或由 BytesNode::replace() 在内部拆分为两个动作。
  • 每个动作提供 execute(Operation)，Operation 为 Action 中的枚举，取值为执行、撤销、重做之一。
  • 动作按 ID 引用节点以便序列化，运行时另存非持有指针以避免查表。
  • 动作不理解业务语义。新增业务操作时组合现有动作，而非新增动作类型。

转移

转移在同一模型内把节点从一个父节点移到另一个父节点，节点的地址与 ID 不变。用于需要保持身份的场合，例如多轨工程中把音符移到另一轨，或把一条 oto 条目改挂到另一个 wav 下：界面中的选区与拖动状态以 ID 记录，删除后插入副本会使其失效。

  • 由目标容器发起，被转移节点的当前位置即为源位置：VectorNode::transferIn(int index, const std::vector<Node *> &nodes)、StructNode::transferIn(int slot, Node *node)、MappingNode::transferIn(const QString &key, Node *node) 返回转移是否执行，SheetNode::transferIn(Node *node) 返回新键，未执行时返回 0。源为 VectorNode 时，一次转移的多个节点须为同一父节点中的一段连续区间。
  • 源父节点与目标父节点须不同，同一父节点内的重排使用 VectorMove。二者都须在树中，目标不能是被转移节点本身或其后代（约束 5、6）。环检查沿目标父节点向上遍历祖先，代价与树的深度成正比。
  • 目标为槽位或键时，该槽位或键须为空。需要替换已有内容时，由调用方先删除、再转移，二者属于同一事务。
  • 违反上述条件的转移被拒绝：不产生动作，并以返回值告知调用方。条件包括被转移节点为根、源与目标为同一父节点、目标为被转移节点本身或其后代、目标槽位或键已被占用，以及多个节点不构成源中的一段连续区间。拒绝而非断言，是因为这些条件可能来自用户的拖放操作，调用方据返回值给出提示即可。在事务之外或对自由节点调用则是编程错误，以断言检查。
  • 位置由各容器类型的转移端点描述：VectorNode 为下标，SheetNode 为键，StructNode 为槽位，MappingNode 为键。端点负责从容器中取出节点和把节点放回，转移动作只在两端之间搬运，并更新节点的父节点。
  • 转入 SheetNode 时，键在首次执行时由该节点分配并记录在动作中，重做时使用同一个键。键不复用，因此不会冲突。转出后原键不再使用。
  • 转移动作不持有节点，序列化时只写出两端的父节点、位置与节点 ID，不写出子树。
  • 通知给出源与目标两端，观察者据此把同一节点从一处移到另一处，而不是删除后新建。撤销时两端互换。

事务

model.beginTransaction();
notes->remove(12, 3);
notes->insert(20, std::move(moved));
model.commitTransaction({{"message", "Move 3 notes"}});
  • 事务外修改模型中的节点是编程错误，以断言检查。
  • abortTransaction() 按相反顺序撤销事务内的全部动作，树恢复为事务开始前的状态。动作持有的节点随动作一同销毁，因此在事务中插入的节点于中止时析构。
  • 不含动作的事务不产生撤销步骤。
  • 提交前的一致性校验由调用方负责：校验失败时调用方中止事务。模型不提供校验回调，因为约束属于业务语义。
  • 事务消息为字符串到字符串的映射，由存储引擎与事务一同保存。

通知

模型提供订阅接口：

class ModelObserver {
public:
    virtual ~ModelObserver();
    virtual void actionAboutToApply(const Action &action, Action::Operation operation);
    virtual void actionApplied(const Action &action, Action::Operation operation);
    virtual void stepChanged(int step);
    virtual void nodeAboutToBeDestroyed(Node *node);
    virtual void aboutToReset();
    virtual void resetFinished();
};
  • 观察者由 Model::addObserver() 注册，按注册顺序通知。观察者的生存期由调用方负责，在被移除或模型析构之前须保持有效。
  • 通知给出实际发生的变化。 撤销一次插入，观察者看到的是删除。每个动作类型提供按方向解释的访问函数，参数为 Action::Operation，默认值 Execute 给出动作记录时的含义，例如 VectorInsDelAction::isInsertion(operation)、VectorMoveAction::index(operation) 与 destination(operation)、PropertyAction::newVariant(operation)、TransferAction::source(operation) 与 target(operation)。观察者不必自行取反。
  • 事务中的每个动作在执行时即发出通知，界面随之更新。中止事务时，撤销产生的通知同样发出。随动作首次进入模型的节点在动作执行时才获得 ID，因此 actionAboutToApply 中这些节点的 ID 为 0。
  • 转移的位置从容器中读取：在 actionAboutToApply 中，被转移节点位于源位置，在 actionApplied 中位于目标位置。
  • stepChanged 在产生步骤的提交、撤销与重做之后发出。空事务与中止的事务不改变步骤，不发出该通知。
  • nodeAboutToBeDestroyed 在事务被截断、淘汰或中止，其动作持有的节点即将析构时发出。被析构子树中的每个节点各通知一次，父节点先于子节点，通知期间整棵子树完好。存储引擎析构 Transaction 时由其析构函数发出，因此自定义的引擎无需另行处理。模型重置与析构时只发出 aboutToReset，不逐个通知节点，见「析构顺序」。
  • 通知回调中修改模型是编程错误，以断言检查。回调中可以读取模型，也可以修改自由节点。
  • qsubstate 提供 QObject 适配器 ModelNotifier，将上述回调转换为同名的 Qt 信号。信号参数中的指针只在发出期间有效，因此只支持直接连接。

ID

  • 类型为 std::uint64_t，0 表示自由节点。
  • 节点首次进入模型时由模型分配，此后在该节点的生命周期内不变，包括撤销与重做。
  • 在一个模型的生命周期内单调递增，不复用。持久化后恢复的模型从日志中记录的最大值继续分配。
  • clone() 产生的副本是自由节点，没有 ID，进入模型时获得新 ID。clone() 不复制 ID，恢复时按指定 ID 创建节点属于反序列化的职责，与复制无关。
  • 模型维护从 ID 到节点的索引，包含树中的节点和动作持有的节点。节点析构时从索引中移除。

存储引擎

模型负责执行与通知，存储引擎只负责保存历史记录。 执行动作、发出通知与维护 ID 索引都在模型中进行，通知与状态切换因此集中在一处。引擎的接口如下：

class StorageEngine {
public:
    virtual ~StorageEngine();

    virtual void commit(Transaction transaction) = 0;
    virtual Transaction *previousTransaction() = 0;
    virtual Transaction *nextTransaction() = 0;
    virtual void reset() = 0;

    virtual int minimumStep() const = 0;
    virtual int maximumStep() const = 0;
    virtual int currentStep() const = 0;
    virtual std::map<std::string, std::string> stepMessage(int step) const = 0;
};
  • commit() 接收事务的全部所有权，包括动作持有的节点。截断重做分支与淘汰最早步骤由引擎决定，被丢弃的事务在引擎中析构，其持有的节点随之析构。
  • 当前步数是位于两个事务之间的游标。previousTransaction() 返回游标前面的事务，即撤销时要执行的事务，并使游标后退一步。nextTransaction() 返回游标后面的事务，即重做时要执行的事务，并使游标前进一步。二者与列表迭代器的同名函数语义相同。模型按相应方向执行返回的事务并发出通知。无法撤销或重做时返回空指针。
  • 第一阶段只实现 MemoryStorageEngine，它保留不超过上限的事务数，提交时先截断、再淘汰最早的事务。

持久化接口

以下各项在第一阶段即须按本节规定实现，因为它们决定节点、动作与模型的公开接口。WAL 引擎本身在第二阶段实现。编解码器的接口位于 Codec.h：Codec 登记可解码的类型，Encoder 与 Decoder 在一个 BinaryStream 上读写节点与动作。读写失败记录在流的状态中，解码失败时已部分解码的节点随即析构，不留在模型中。

  1. 每个动作均可序列化。 动作写出其类型、所引用节点的 ID 和数据。动作在未执行时持有的节点，即插入的子树、新的根与赋值的新值中的子节点，写出完整内容，因为恢复时从检查点向后重放须重建这些节点。其余节点，包括删除的节点、被替换的旧值中的子节点与转移的节点，只写出 ID，见第 7 项。写出的形式只有一种，与动作当时的状态无关。

    • 插入的子树写出的是写出时的内容，只在后续动作修改它之前等于插入时的内容。因此引擎在 ModelObserver::actionApplied() 报告动作首次执行时写出动作，而不是在提交时写出整个事务。
    • 转移动作写出两端的父节点 ID 与位置，位置由各容器的 TransferEndpoint::write() 写出、Node::readEndpoint() 读回。转入 SheetNode 的键在首次执行时已分配，随动作写出。
    • 解码时须给出动作的状态（Action::State）：Unapplied（未执行）或 Applied（已执行），对应「记号」一节中位于当前位置之后或之前的动作。状态决定动作持有哪些节点（约束 2），解码因此按状态分为两种方式，与 AceTreeModel 读回历史时插入操作只读 ID（readBrief()）的做法相同：
      • 未执行的动作从内容新建它持有的节点，其余节点按 ID 在模型中查找。从日志向前重放的动作即处于这一状态。
      • 已执行的动作所插入的节点已在模型中，按 ID 查找并跳过其内容。为此节点记录在内容之前写出内容的长度。它删除的节点与被替换的旧值中的子节点由它持有，从 NodePool 中按 ID 取得所有权。
    • NodePool 存放已解码进入模型、但既不在树中也不属于任何动作的节点。引擎恢复检查点之前的历史时，把检查点中已执行动作持有的节点解码进池中，再以该池解码已执行的动作，各动作取走各自持有的节点，每个节点因此恰有一个所有者（定理 1）。解码全部动作后池须为空，否则检查点与日志不一致。模型的 ID 索引只用于查找，不承担所有权，这正是 AceTreeModel 提前释放缺陷的成因，见「与 AceTreeModel 的对照」。
    • 解码的动作只对它处于该状态时的树有效，由调用方保证。重放时，引擎经 NodePrivate::execute() 在事务中执行解码的动作，重放插入或转移时 SheetNode 的键计数器随之前移。

  2. 每个节点均可序列化，包括其类型、ID 与全部子节点。检查点即为整棵树的序列化，加上已执行动作持有的节点，后者由第 7 项的 forEachHeldNode() 枚举。SheetNode 同时写出键计数器，使恢复后的节点不复用已删除的键。不指定模型解码时，节点解码为自由节点，ID 被忽略，可用于剪贴板等场合的复制。

  3. 编解码器按类型注册。 核心节点与动作由 Codec 登记，MappingNode、qsubstate 的动作与 QVariant 的编码由其子类 QCodec 提供，用户节点类型由调用方注册。QVariant 的编码分为两类：

    • bool、整数（int、qint64 等）、double、QString 与 QByteArray 由 qsubstate 以固定格式自行编码，不依赖 Qt 的序列化格式。整数统一以 64 位写出，并记录原类型，读取时恢复。QString 按 UTF-16 码元写出，未配对的代理项也能原样往返，相等判断因此在往返后成立。
    • 其他类型，包括调用方的自定义类型，经由 QDataStream 编码。流版本固定为 QDataStream::Qt_5_15（QCodec::dataStreamVersion），否则同一日志在不同 Qt 版本下的编码不同。选择该版本是为了之后支持 Qt 5 时两个版本写出的数据相同。自定义类型以类型名记录，调用方须在读写之前注册该类型及其流运算符。没有流运算符的类型无法写出，写出失败。类型改名或删除后，记录了该类型的日志无法读取，这一责任属于调用方。

    Property 只以 QVariant 表示标量，不另设一个封闭的标量类型。两种表示并存时，同一个值有两种存法，相等判断与「值未改变时不产生动作」的规则都须另作规定，而 Property 仍依赖 Qt，封闭类型的主要收益无法取得。

  4. 反序列化能够按指定 ID 创建节点，并将模型的 ID 计数器恢复到日志中的最大值。解码的节点带着记录的 ID 进入模型，但不进入树。ID 为 0、重复或已存在于模型中时解码失败。

  5. 历史记录的位置由引擎决定。 模型只通过 previousTransaction() 与 nextTransaction() 取得事务，不假定全部历史都在内存中。WAL 引擎可以将早期步骤换出到磁盘，需要时再读入。

  6. 恢复由引擎发起：引擎读取检查点与日志，构造根节点与历史记录，再交给模型。入口为 Model::restore(root, lastId)：模型须没有树，例如在 reset() 之后。它安装解码的根，不产生动作，保留引擎已恢复的历史记录，并把 ID 计数器提高到引擎记录的最大值，使已析构节点的 ID 不被复用。

  7. 事务能够枚举其持有的节点。 删除类动作在日志中只写出节点 ID，被删除节点的内容由引擎写入检查点，与 AceTreeModel 相同。引擎据此收集一段历史中被删除的节点。

以下事项留到第二阶段的设计中确定：日志与检查点的文件格式、同步或异步写入、检查点的间隔、写入失败时的处理，以及 fsync 的时机与步数记录的原子更新方式。AceTreeModel 的日志后端是首要参考，但其写入只调用 QFile::flush()，不保证断电后数据完整，见 References.md。

库的划分

库 依赖 内容
substate 标准库 节点基类、VectorNode、SheetNode、BytesNode、ArrayNode<T>、动作、事务、模型、存储引擎、编解码器接口
qsubstate substate、Qt Core Property、StructNode、MappingNode、QVariant 编解码器、Qt 信号适配器

Qt 依赖只来自 Property 中的标量。以一个不依赖 Qt 的封闭类型取代 QVariant，可以把 StructNode 与 MappingNode 移入核心库，但没有内存收益：由 bool、long long、double、std::string 组成的 std::variant 同为 40 字节。代价则是 Qt 调用方每次读写字符串都须在 QString 与 UTF-8 之间转换。因此保留现有的划分。

qsubstate 目前只支持 Qt 6，Qt 5 的支持在之后添加。两者 QVariant 的类型查询接口不同，添加 Qt 5 支持时，QVariant 编解码器按两套接口分别实现，qsubstate 的测试在两个版本上均须通过。

测试

  • substate 使用 Boost.Test，qsubstate 使用 QtTest，与 stdutau 和 HelloUTAU 的惯例一致。
  • 一个测试文件对应一个头文件。
  • References.md 列出的每个缺陷均有对应的测试，并以突变验证：将缺陷放回后测试须失败。
  • 每种动作均测试：执行、撤销、重做后树与预期相同，节点地址与 ID 不变，通知的内容与方向正确。
  • 所有权的检验见「所有权的正确性」中的「可执行的检验」：存活节点集合与参照实现逐步比较、ID 索引的条目数、长历史测试、AceTreeModel 探针的回归测试，以及 AddressSanitizer。
  • 一个随机测试：随机生成一串事务并随机撤销重做，与一个简单的参照实现（每步保存整棵树的深拷贝）逐步比较。

公开接口与扩展接口

只使用 Model 与现有节点类型的调用方只需要公开头文件：修改树、转移节点、撤销重做与订阅通知都通过公开接口完成。include/*/private/ 中的头文件只供扩展者使用，即实现新的节点类型或动作类型：

  • 支持转移的新容器类型覆盖 Node::endpointOf() 与 Node::readEndpoint()，并实现 Transfer_p.h 中的 TransferEndpoint。
  • 新的动作类型经 NodePrivate::execute() 交给模型执行，由模型发出通知并加入当前事务。存储引擎重放解码的动作时同样使用该函数。

公开头文件不引用私有头文件。继承现有节点类型而不改变其存储的类型，例如测试中的计数节点，同样不需要私有头文件。

代码规范

采用 HelloUTAU 与 stdutau 的规范（helloutau/docs/Development.md 为权威文档），包括注释的正式文体。差异如下：

  • 不使用 qmsetup，构建脚本只使用 CMake 自身的功能。
  • 命名空间保持 ss。
  • 全局头文件保持 substate_global.h 与 qsubstate_global.h。
  • 文档位于 docs/。

实施阶段

第一阶段实现本文档规定的全部内容，历史记录只保存在内存中：所有权模型与 ID 索引、全部节点类型、转移、通知与 Qt 适配器、编解码器与序列化。存储引擎只有 MemoryStorageEngine，FilesystemStorageEngine 为第二阶段保留的空文件。

第二阶段实现 WAL 引擎，另行设计，未定事项见「持久化接口」的末段。第二阶段只新增存储引擎，不修改节点、动作与模型的公开接口。