search

phenomLi / Blog

Comments, Thoughts, Conclusions, Ideas, and the progress.
219 stars 17 forks source link

一些思考：项目的实现到重构 #37

Open phenomLi opened 4 years ago

phenomLi commented 4 years ago

前段时间一直在做实验室的项目，也就是数据结构可视化的内容。目前来讲第一版已经完成了，然而在不断增加的需求下，代码逐渐变得不可控，于是我毅然选择了重构（其实基本上是换一种思路重写了），也就是第二版的开发。写这篇文章就是想把我在构建这个数据结构可视化系统从开始的构思，到发现问题（为什么要重构），最后用什么的思路重构的这个过程记录下来，我觉得很有必要。


初始需求

根据导师的意思，在我们已有一个在线webIDE的情况下，构建一个可视化系统，在用户调试的过程中，对用户所编写实现某种数据结构的代码进行可视化，比如用户写了一棵二叉树，就在可视化区域绘制出这棵二叉树；其次，在每一步调试中，若发生数据结构的变化，可视化区域都要将前后两次变化用动画呈现出来，换句话说就是不能直接擦除旧的二叉树，又生成一棵新二叉树覆盖上去。最后，暂时只需支持二叉树和链表。

对这个需求抽丝剥茧，提取核心，可以得到以下信息：


构思

那么，从这两个信息如何往代码结构层面转变？首先，对于初始状态，不难想到，可将可视化系统视作一个函数：Sources => View，这里 Sources（源数据） 指的是 一种描述某种数据结构信息的数据，作为可视化系统的输入， View（视图） 显然就是值可视化系统所绘制出的内容。其次根据单一职责原则，这个可视化系统只需实现从Sources输入到绘制View这个过程，至于如何识别用户写的是什么数据结构，Sources从哪里生成，这不是我所关心的内容。
其次，根据需求，每一次数据结构变化都理应生成一份新的Sources，重新输入可视化系统。但是此时不能直接输出View，即不能直接进行可视化绘制，因为要基于上一次的View进行更新。熟悉React的朋友应该都能联想到这种基于上一状态进行差异更新的机制的核心在于前后数据的差异识别（differ），同样地我也是使用这种思路对可视化系统进行图形更新。那么，对于后续状态，可以抽象为：Sources => differ => View。

Sources作为可视化系统的输入，结构和格式应该由可视化系统进行约定，使用可视化系统前应将编译器的到的数据转化为Sources格式。以二叉树为例，初步设计的Sources格式如下（经过简化）：

class Source {
    id: nodeID,
    data: any,
    leftChild: nodeID,
    rightChild: nodeID
}

以上Source对象简单地表示一个二叉树结点，使用结点ID（nodeID）表示结点间的逻辑关系，多个Source组成Sources。但是，直接使用Sources经过某种运算得到二叉树View是不现实的。 首先，绘制二叉树必须需要根据某种树形布局算法，布局算法需要记录坐标位置。其次，Sources对于结点间关系的描述不够清晰，而且也没有显式地给出次双亲，主双亲之类的重要信息。说白了就是Sources的信息过于简陋隐晦，不好直接处理。

也就说可视化系统中应该需要一种贯穿整个过程的结构，用于详细描述Sources的同时，还能保存布局所需的位置信息，同时最好能保存所使用可视化系统所使用的图形库（我使用的是百度的zrender）对应的图形实例。再以二叉树为例，我在可视化系统内部增加了一种对象，用于完整地描述二叉树结点，其结构大概如下：

class Node {
    // 结点id
    id: nodeID;
    // 结点数据域
    data: any;
    // 孩子结点
    children: Node[];
    // 主双亲
    parent: Node;
    // 次双亲
    secondaryParent: Node;

    // x坐标
    x: number;
    // y坐标
    y: number;
    // 是否可见
    visible: boolean;
    // 该结点对应的可视化图形
    zrenderShape: Shape;
}

Node对象包含了描述一个二叉树结点的大部分信息，其中为了于链表结构做兼容，我使用数组保存孩子结点。一个Source对应一个Node，同样由于保存了位置信息，可很容易地在布局之后对上一次的位置进行对比，或者上一次可见的状态，对结点进行位置更新或控制其可见性。

现在知道了在初始状态，输入Sources之后需要将Sources转化为Node的集合Nodes才能进行可视化绘制，但是对于后续状态，是要生成Nodes然后和上一批Nodes进行differ吗？其实不应该这样做，每次differ前都生成一批新的Nodes可能会产生一定的开销（虽然也不大），同时也无需这样做，Sources中的信息足够进行differ了。所以理想的做法是对Sources进行differ，然后使用differ得到的信息更新Nodes。所以现在一套组合拳下来，可视化系统的两种状态可以抽象为：

最后，得到流程图如下：


so far so good


问题

按照以上思路，我完成了第一版可视化系统的开发，支持二叉树和链表。然后做开发的不可能这么顺风顺水。。。之后一些需求被提出来，比如添加用户与视图的交互，外部指针等，还有最重要的，多数据结构的支持。目前来讲支持的数据结构太少了，对于数组，图，哈希表等最终都需要被支持。

同时随后我渐渐发现了一些致命的问题，随着项目的膨胀，代码之间的耦合关系和类与类之间的调用关系变成了一张大网，代码开始变得混乱。我开始怀疑当初的思路从根本上是有缺陷的。

1. Node对象的设计

回过头来看Node的设计：

class Node {
    // 结点id
    id: nodeID;
    // 结点数据域
    data: any;
    // 孩子结点
    children: Node[];
    // 主双亲
    parent: Node;
    // 次双亲
    secondaryParent: Node;

    // x坐标
    x: number;
    // y坐标
    y: number;
    // 是否可见
    visible: boolean;
    // 该结点对应的可视化图形
    zrenderShape: Shape;
}

其中可以发现，children，parent，secondaryParent等属性，是用于描述二叉树的结构的，属于数据结构本身的数据。而x，y，visible，zrenderShape等属性是用于描述结点样式的，属于视图相关数据。而且这已经是简化过的代码，在实际项目中Node有10几个属性。将属于数据结构本身的数据和视图数据放在一起，表明了修改二叉树逻辑结构的代码也要和修改其视图的代码也要混在一起，比如下面一段在Node类中的伪代码，该方法用于给Node添加右孩子节点：

addRightChild(child: Node) {
    this.children[1] = child;
    child.parent = this;
    child.setVisible(true);
}

可以看到该方法在添加孩子结点的同时又将孩子结点设为可见。实际中的情况要比例子中要复杂得多，混合了主/次双亲的判断和结点动画的一些适配代码。同样复杂的还有类与类之间某些属性的依赖。

2. 扩展性（复用性）

这是我所认为的最致命的设计缺陷。正如前面提到，目前该可视化系统仅仅支持二叉树和链表，由于二叉树和链表具有高度的相似性，所以我在实现的时候，最大程度地使链表可视化复用了二叉树可视化的大部分代码，除了布局方法外，Node，differ等基本都和二叉树实现了公用一套。

然而，数组可视化呢？

数组根二叉树，链表结构有本质上的不同，再一次看回Node的设计，什么children，parent基本都是为链式数据结构服务的，数组基本无法复用Node类，更别说栈，哈希表了。这意味着初设计好的二叉树，链表外，其他类型的数据结构都要重新写一套代码。如果这个项目有多人接手的话，代码基本上就群魔乱舞了。

3. 交互

一开始交互简单的时候（只有缩放），交互代码可以直接写在可视化逻辑里面。然后后面随之而来还有

等交互需求，如果都和可视化逻辑混在一起，估计项目就得爆炸了。理想的做法是将交互和可视化逻辑分离。


重构（重写）

要解决上面三座大山，在现有的架构上进行修改是基本不可能解决的，即使解决了问题3，问题1，2依然属于底层设计缺陷。所以我要从底层设计进行改动。
怎么改呢？重新审视一下问题1，2：

  1. 显然属于视图的数据和属于数据结构本身的数据不应该存在于同一个结构，应该对其进行拆分为两种结构，分别存在于两个阶段，什么阶段呢，未定

  2. 即使像数组这类与链式结构有着较大差别的结构，即使无法复用之前的代码，其可视化过程依然可以抽象为：

    • 初始状态：Sources => 某种中间结构 => View
    • 后续状态：Sources => differ => 某种中间结构 => View

    也就是说无论什么数据结构，它的整个可视化流程都是一样的，只是由于不同数据结构的Sources不同，导致生成的中间结构不同，同样differ的方式也不同，导致了代码基本无法复用。但是也可以想到，既然可视化的流程是相同的，就不难抽象出一套适用于任何数据结构的框架，来专门负责这个流程，至于具体内容如何，未定

得出结论：需要抽象出一套易扩展，低耦合的可视化框架。

由1可以知道，某种中间结构应该再被拆分为两中结构，分别保存数据结构本身的数据和视图相关的数据，两种结构对应两个阶段，一个用于生成与数据结构本身数据相关结构，一个用于生成与视图数据相关的结构。回想起Web的发展历程，也是由业务逻辑，数据和视图控制代码混写的阶段到业务逻辑，数据和视图分离的MVVM阶段，本质思想就是将应用的数据（或称状态）从视图控制逻辑中抽离，使用数据本身去驱动视图，用户输入为主动，数据为核心，而视图变为被动的监听者（listener），形成了一个很明显的先后关系：数据 => 视图，取个好听点的名字就是Model（数据模型）=> ViewModel（视图模型）。

类比MVVM，可视化系统中要做到数据与视图分离，自然地也应当引入Model => ViewModel的理念。其中Model对应“去除视图相关数据的某种中间结构”的集合。这句话怎么理解呢？以二叉树的Node为例，理想应该是：

class Node {
    // 结点id
    id: nodeID;
    // 结点数据域
    data: any;
    // 孩子结点
    children: Node[];
    // 主双亲
    parent: Node;
    // 次双亲
    secondaryParent: Node;
}

此时的Node就称为“去除视图相关数据的某种中间结构”，只保存与数据结构本身相关的数据，至于坐标位置等不应该涉及。对于其他的数据结构，比如数组，其“去除视图相关数据的某种中间结构”有可能叫Slot，但是无论叫什么都好，其结构都应该与Node是不一样的，对于这些Slot也好Node也好的“去除视图相关数据的某种中间结构”，我统称其为Element，Element由用户自定义，Model即由多个Element组成。

而对于ViewModel，于基于DOM的web开发不同，基于Canvas的可视化系统并非使用像JSX或VirtualDOM这类可以声明式地描述View的工具表示ViewModel，而是使用“封装图形库中的图形对象”，比如说二叉树中的结点我想用一个圆形表示，那么我就创建一个圆形类供其使用：

class Cicle {
    // 结点id
    x: number;
    // 结点数据域
    y: number;
    // 半径
    radius: number;
    // 颜色
    color: string;

    // ...颜色字体等属性

    // zrender图形实例
    zrenderShape: zrenderShape;
}

上面zrenderShape就属于图形库（zrender）中图形，Circle类就是封装图形库中的图形对象。在可视化中应当内置多种像Circle这样的对象，比如Rect（矩形），Isogon（正多边形）等，我将这类“封装图形库中的图形对象”统称为Shape，Shape由可视化框架内置，ViewModel即由多个Shape组成。


搞出Element和Shape的概念有什么好处吗？

  1. Element对应Model，只表示数据结构相关信息；Shape对应ViewModel，只表示视图与布局的相关信息。抽象出了基于Canvas的可视化系统的Model和ViewModel
  2. 原本的Node中保存了zrenderShape，即一个Element对应确定的Shape，现在将Shape与Element的关系砍断，一个Element，或者说可视化过程中，要使用哪些Shape就变得灵活可控了
  3. Element和Shape分开管理，逻辑结构相关代码和视图相关代码天然隔离


现在这套可视化框架的流程可以抽象为：

其中=>符号，我现在更倾向于将它理解为映射。一种Sources可以映射为一种Model，一种Model映射为一种ViewModel，一种ViewModel映射为一种View。之间没有从属关系，只有映射关系，先后关系，因果关系，一种pure function的思想。

不难发现我没有写后续状态的流程表示，因为还有一个问题没有解决：differ阶段应该放哪？我们要在不同数据结构中尽可能抽取公用部分，由于Sources和Model都是用户定义的，如果对Sources或者Model进行differ，那么基本上不可能复用differ。其次，因为最后的update是在View中进行的，对Sources和Model中间隔了个ViewModel，differ最终还是要收敛到ViewModel。

所以第四个好处就是：

  1. 由于Shpae是框架内置的，因此Shape中的结构是确定的。无论Element前后有多少变化，收敛到Shape中都只会表现为位置，可见性和样式三种变化。对ViewModel进行differ可实现简单和可复用

现在可视化框架完整的流程可以表示为：

假如基于该框架扩展一个二叉树的可视化方法，只需要三步：

  1. 定义二叉树所需的Element
  2. 编写Sources => Model函数的代码
  3. 编写Model => ViewModel函数的代码

在代码层面上体现为继承：

class BinaryTreeNode extends Element {
    // .....
}

class BinaryTree extends Framework {
    mapModel(Sources): Model { 
        // ...
        return Model;
    }

    mapViewModel(Model): ViewModel {
        // ...
        return ViewModel;
    }
}

本质上你只需要写一个类和两个函数就可以完成一个新的数据结构可视化，框架帮你干了Elememnt管理，Shape管理，differ，patch，将ViewModel绘制成View和配置项注入等工作。

以上都是我目前为止已经完成的内容，对于问题3交互，我的初步设想是借鉴VS Code的插件机制，将每一种交互视为一种可插拔的插件，然后通过交互管理器同一管理。框架本身只暴露某些api给交互管理器，并且只通过bus通信，低耦合高内聚，河水不犯井水。但是具体细节还没尘埃落定。

最后

我一直觉得程序员就是一个接线员，写代码就像给两台有大量接口的机器接线，线接错了就是出现bug了，都接对了就是实现功能了，然而在接对得情况下，如何把线接得不乱，线与线之间理得清清楚楚，这就是重构的力量，就是设计模式的力量。接着接着发现线乱了，就要不时地停下来理一理。

Thinking > coding


--- EOF ---