【SDU Chart Team - Core】提交过程与提交算法_html-js-css

提交过程与提交算法提交过程

SVGI中引入了提交过程，用于进一步优化渲染。

提交过程

提交指的是将此阶段被修改的内容提交到新的版本，得到所有更改，并对此进行优化。

假设当前的DOM树为A，过去版本的DOM树为B，那么提交等价于A-B的Diff过程。

但是显然，如果保存另一个过去版本DOM树B的拷贝，则开销太大了，因为此前的拷贝 *** 作中将要拷贝全部的属性和树形结构，时间复杂度是 O ( a n ) O(an) O(an) 的。由于提交的内容是对自身修改，我们不妨可以直接记录修改，提交被修改的内容。

记录修改

修改来源于下面两种方式：

属性的修改

属性的修改中包括原生HTML的修改。

属性的修改不需要额外定义提交区，因为此前的属性类中已经实现了提交区。显然，如果采取遍历手段，即使是if…else…枚举，时间复杂度也是 O ( a ) O(a) O(a) 的。通过记录是否被修改，能优化此复杂度。

首先是简单的赋值。这个可以通过回调函数完成，即被赋值后调用回调函数，则可以隐式地告知被修改了。

然后是绑定。这个没法直接判断是否被修改，每次提交时都必须进行一次判断。

所以最终的处理方法是为每个属性分配一个id，创建两个id集合，分别表示提交前被绑定的和被复制的属性。属性类的回调函数即对应维护这两个集合。提交时，遍历集合，使用提交函数对提交区值进行检查，判断是否真的被修改了。

时间复杂度为 O ( b + d ) O(b+d) O(b+d)， b b b为被绑定的属性的个数， d d d为被赋值的属性的个数。最坏情况下是 O ( a ) O(a) O(a)，但一般远小于 O ( a ) O(a) O(a)。

子元素的修改

使用额外的提交区。列表inner_elements表示提交后的子元素表，inner_elements_commit表示当前子元素表。所有关于子元素的维护都是在inner_elements_commit上进行的，提交后inner_elements等于inner_elements_commit。

关于子元素的提交的判断和决策，只是对前面的DOM Diff算法做出了一点修改，即不需要考虑是否被修改，只需分离出被增删的元素。

提交算法算法伪代码

A.class="superseo">commit：
- 提交属性
    1. 遍历待提交集合
        1. 属性为默认值 => 重置属性
        2. 属性不为默认值 => 设置属性 
- 递归提交inner_elements_commit
- 提交inner_elements：比较inner_elements和inner_elements_commit
    1. 比较inner_elements，跳过tag相等的
    2. inner_elements中剩下的（被删除）
    3. inner_elements_commit中剩下的（被添加）
    4. 按照映射重排序
- 更新哈希

和DOM Diff算法相似。区别主要有以下几点：

提交算法的对象是自身，而DOM Diff是两颗树。
因为提交的目的是从旧版本到新版本，所以都是在一棵树上进行的。

提交算法是后序遍历，DOM Diff是前序遍历。
提交算法没法剪枝，因为它无法判断子树是否被修改。DOM Diff可通过依托子树哈希剪枝。

提交算法的只需分离被增删的元素，DOM Diff还要分离被修改的元素。
因为提交算法后序遍历，先提交了孩子。inner_elements和inner_elements_commit保存的是指针。所以对于一个仅被修改的孩子，它在inner_elements和inner_elements_commit同时存在，内容在回溯后是完全相同的。

但是注意，反过来不一定成立，即相同内容不一定是相同的指针，如果仅以指针进行配对，代价可能更高。所以仍然需要使用贪心手段配对标签相同的孩子，以达到最小代价。

提交算法需要更新哈希，而DOM Diff不需要
这是显而易见的，因为哈希记录的旧版本哈希。提交是将旧版本变更为新版本，相当于集中进行修改，是一种写 *** 作，因此需要更改哈希；而DOM Diff的两棵树都是参照未提交前的版本进行的，是只读的。

复杂度分析

最坏情况下遍历全部的属性和整棵树，是 O ( a n ) O(an) O(an)的；最好情况和平均情况的复杂度是 O ( n ) O(n) O(n) 的。

如果没有绑定，和DOM Diff一样能达到 O ( l o g n ) O(logn) O(logn)；但是为了方便使用，还是决定舍弃性能。

核心代码

提交

const std::string SVGIElement::commit() {
    std::stringstream ss;

    _updated_raw_html = get_raw_HTML() != RawHTML.get_commit();
    RawHTML.commit();
    if (get_raw_HTML() != STR_NULL) return "";

    // attribute differ
    for (auto &i : bound) {
        auto &cmd = _attr_commit[i]();
        if (cmd != STR_NULL) ss << cmd  << std::endl;
    }
    for (auto &i : modified) {
        auto &cmd = _attr_commit[i]();
        if (cmd != STR_NULL) ss << cmd  << std::endl;
    }
    modified.clear();
    
    // recursion
    std::vector<std::string> changed;
    for (auto &p : _inner_elements_commit) changed.push_back(p->commit());
    // extract change relation
    std::vector<int> removal;
    std::vector<int> addition;
    std::vector<std::pair<int, int>> unchanged;
    inner_differ_commit(removal, addition, unchanged);
    // remove
    int m = _inner_elements_commit.size(), n = _inner_elements_last.size();
    int *indices = new int[m], *removed = new int[n];
    std::fill(indices, indices + m, 0); std::fill(removed, removed + n, 0);
    for (auto &r : removal) removed[r] = 1;
    for (int i = 1; i < n; i++) removed[i] += removed[i - 1];
    for (auto &r : removal) ss << "remove " << r - (r > 0 ? removed[r - 1] : 0) << std::endl;
    // append
    for (auto &a : addition) {
        auto svg = _inner_elements_commit[a]->outer_SVG();
        ss << "append " << svg.size() << std::endl << svg << std::endl;
    }
    // changed
    for (auto &c : unchanged) {
        auto &a = c.first; auto &b = c.second;
        auto &s = changed[a];
        if (s == STR_NULL) continue;
        ss << "child " << b - removed[b] << std::endl;
        ss << s;
        ss << "parent" << std::endl;
    }
    // sort
    for (auto &c : unchanged) {
        auto &a = c.first; auto &b = c.second;
        indices[b - removed[b]] = a;
    }
    for (int i = 0; i < addition.size(); i++) {
        auto &a = addition[i];
        indices[unchanged.size() + i] = a;
    }
    bool ordered = true;
    for (int i = 0; i < m && ordered; i++) if (indices[i] != i) ordered = false;
    if (!ordered) {
        ss << "sort \"";
        for (int i = 0; i < m; i++) {
            ss << indices[i];
            if (i < m - 1) ss << ",";
        }
        ss << "\"" << std::endl;
    }
    delete[] removed; delete[] indices;

    // commit inner changes
    _inner_elements_last.clear();
    SVGElement::set_inner_elements({});
    for (auto &p : _inner_elements_commit) {
        if (p->_updated_raw_html) p->_updated_raw_html = false;
        _inner_elements_last.push_back(p);
        SVGElement::add_inner_element(p);
    }

    return ss.str();
}