可逆计算理论中的 Delta 合并算法

可逆计算理论明确指出全量是差量的特例，我们可以基于差量的概念重构整个软件生成过程。为了最大化 Delta 差量概念的价值，差量之间的运算应该是可以由软件自动完成，而无需人工介入。在 Nop 平台中，我们定义了一个可以保持节点顺序的自动化差量合并算法，所有的树状结构的对象都采用这个算法实现差量合并。

合并算子 x:override

节点合并时缺省采用 merge 模式：

1. 节点属性按名称进行覆盖

2. 如果是不允许重复的子节点，则按照名称进行覆盖

3. 如果是允许重复的子节点，则按照唯一键属性进行覆盖

例如:

<entity name="test.MyEntity" tableName="MY_ENTITY">    <comment>注释内容</comment>    <columns>        <column name="phone3" label="xx" />    </columns></entity>

entity 节点下只允许一个 comment 子节点，以及一个 columns 子节点，所以合并的时候，这两个子节点都是按照名称进行合并。然后递归处理这两个子节点的合并情况时，按照 XDef 元模型中的定义，columns 的子节点是允许重复的，所以它将按照 name 这一唯一标识属性进行合并。在上面的例子中，phone3 字段的 label 属性会被定制配置自动覆盖。

x:override的所有值都在XDefOverride类中定义。

我们常用的合并模式有如下几种：

• remove: 删除节点

• merge: 合并属性和子节点

• replace: 整体替换

• merge-replace: 合并属性，替换子节点或者 content

• append: 合并属性，追加子节点或者 content

• prepend: 合并属性，前插子节点或者 content

• bounded-merge: 基本与 merge 类似，但是它额外限定了合并结果的范围，只保留基础模型和派生模型中都存在的子节点。

例如:

<grid>    <cols x:override="bounded-merge">        <col id="a" width="30"/>        <col id="b" width="20"/>        <col id="c" width="50"/>    </cols></grid>

如果 cols 的合并模式设置为 bounded-merge，则合并后只会具有三个节点，所有仅在基础模型中存在，但是在派生模型中不存在的列都会被删除。如果不配置x:override属性或者配置x:override=merge，则表示新增或者覆盖子节点，最终 cols 的子节点个数可能不是 3，而是大于 3。

保序算法

合并列表类型的子节点时会尽量保持节点在派生模型以及基础模型中定义的顺序。比如如果我们想在节点 a 的后面追加一个节点 b，则可以使用如下配置

<cols>    <col id="a" />    <col id="b" width="30" label="test" /></cols>

合并算法规定，如果节点 a 在基础模型中存在，且节点 b 是一个新节点，则它会紧贴着节点 a 插入到结果集中。合并算法会严格保持派生模型中指定的节点顺序，同时尽量保持在基础模型中的节点顺序。具体来说，合并列表时会先将两个列表顺序拼接在一起，然后再根据节点重叠情况将列表分成几个连续的区块，然后再重排区块。

具体示例如下：

1. a=[a1,a2,a3,a4,a5]与b=[b1, a2, b3] 合并， 先得到 all = [a1,a2,a3,a4,a5, b1,a2,b3], 然后发现 a2 重复，需要以 a2 元素为基准移动 a 中的元素得到[a1,b1,a2,b3,a3,a4,a5]，b3 在 b 中紧接着 a2，所以在移动后的序列中也紧接着 a2。

2. 如果 a 与b=[a1, b1, a3, b3]合并，则先得到[a1,a2,a3,a4,a5, a1,b1,a3,b3], 发现 a1,a3 重复，移动后得到[a1,b1,a2,a3,b3,a4,a5]。

3. 基准元素用于定位时可以理解为代表它以及它的后续元素（直到遇到另外一个基准元素为止）。如果 a 与b=[a3,b1,a1]合并，则先得到[a1,a2,a3,a4,a5, a3,b1,a1],现在 b 中 a3 和 a1 颠倒了顺序，先移动 a1 得到[a3,a4,a5, a3,b1,a1,a2]，再移动 a3 得到[a3,b1,a4,a5,a1,a2]
   

测试用例参见 TestMerge.java

兄弟节点之间的原型继承

x:override配置派生模型与x:extends引入的基础模型之间的合并算子。但是除了与外部的基础模型继承内容之外，很多情况下一个列表的子节点之间可能也存在着相似性。例如编辑表单的布局可能与新增表单以及差量表单完全一致，但是也有可能随着需求变化逐渐变得不一致。有些字段可能不允许新建或者修改，但是在查看页面上可以查看。使用x:prototype和x:prototype-override我们可以指定从哪个兄弟节点继承，以及继承时所使用的合并算子。

<!-- base.forms.xml --><forms>    <form id="add">        <layout>            c d         </layout>    </form></forms>
<!-- ext.forms.xml --><forms x:extends="base.forms.xml">    <form id="view">        <layout>            a b        </layout>    </form>        <!-- 与id=view的兄弟节点合并 -->    <form id="add" x:prototype="view" >        <layout x:override="remove" />    </form>    </forms>

原型合并在普通的 Delta 合并之后进行。在上面的例子中，ext.forms.xml 从基础模型中继承了 add 表单的 layout 配置。我们首先通过x:override="remove"删除了继承来的 layout 配置，然后再通过x:prototype="view"表示与兄弟节点 view 表单合并，最终 add 表单中的 layout 是从 view 表单继承得到的 layout。

子节点上的x:extends

除了在 DSL 文件的根节点上可以写x:extends表示可以从指定的基础模型继承之外，在子节点上也可以使用 x:extends。

需要在子节点的 XDef 元模型上配置 xdef:support-extends=true才允许该子节点使用x:extends机制。

<forms x:extends="base.forms.xml">    <form id="add" x:extends="default.form.xml" /></forms>

从根节点的 base.forms.xml 基础模型中我们有可能继承得到一个 add 表单，同时我们又通过x:extends指定了 add 表单从 default.form.xml 继承。而在 default.form.xml 中，它可能继续使用x:extends机制从其他文件继承。如果完整的考虑所有继承节点的情况，则合并算法的实现会变得相当复杂，所以在 Nop 平台的 Delta 合并算法中我们做了一点简化，规定如果节点上明确设置了x:extends，则会自动忽略从根节点上继承得到的节点内容。例如上面的例子中，从 base.forms.xml 中继承得到的 add form 会被自动忽略。

基于可逆计算理论设计的低代码平台 NopPlatform 已开源：

• gitee: canonical-entropy/nop-entropy
  

• github: entropy-cloud/nop-entropy
  

• 开发示例：docs/tutorial/tutorial.md
  

• 可逆计算原理和Nop平台介绍及答疑_哔哩哔哩_bilibili