all articles

Thoughts about front-end dev by implementing a ToDo App(8) -- Better For loop by diffing

2016-12-07 @sunderls

A_ToDo_App

好久不见,到上一篇文章的时候,貌似语法已经有那么点回事了,这一次我们再优化一下for loop的处理。

回顾

关于目前的处理方法在一个ToDo App的前端思考(5)-Data Bind之for loop中已有说明,这里简单回顾一下。假设todo list中添加了两个元素的时候,我们inpect一下所有的watcher:

expression val update desc
ToDO : scope.todos.length text update text 标题
{display: scope.todos.length > 0 ? 'none' : 'inherit'} object update style 空list文案
scope.todos todos.length 根据todos.length变化更新dom list
scope.todos[0].name text 更新text 第一个item的文本
scope.todos[1].name text 更新text 第二个item的文本

也就是说,当todos增加或删除的时候,第三个watcher对dom的数量进行了调整,其他的单个item的watcher会对自身的text进行更新。如果todos在index:0的位置插入一个元素的话,实际上所有的item都进行了更新,虽然肉眼看上去像在首位插入了一个元素。

优化

假定dijest中对旧数组和新数组进行对比,游标分别为i, j。 如果发现数组内部元素有变化,比如第2个位置旧值为a,新值为b, 可以有如下假设:

  1. 如果b是已有的元素的话,可以假定发生了删除;将i移动到b对应的位置。
  2. 如果b是新增的元素的话,可以假定发生了插入;将j移动到i目前元素的位置。

当某一个数组遍历完毕后,如果旧数组有剩余,就是删除;如果新数组有剩余,就是增加。

diff 算法

diff(A, B):
    i = 0, j = 0
    while(i < A.length && j < B.length):
        if (A[i] === B[j]):
            i++, j++
        else if (A.has(B[j]) && index > i):
            remove(A[i, index - 1])
            i == index + 1, j++
        else
            index = B.indexOf(A[i]) || B.length - 1;
            insert(B[j, index]);
            i++, b = index + 1

因为A和B中的每个元素都只遍历了一遍,所以实际复杂度是O(n)。

diff code

首先我们实现上述 diff

/**
 * diff array
 * @param {Array} from
 * @param {Array} to
 * @param {function} add
 * @param {function} remove
 */
const diff = (from, to, add, remove) => {
    let i = 0;
    let totalFrom = from.length;
    let j = 0;
    let totalTo = to.length;

    while (i < totalFrom && j < totalTo){
        if (from[i] === to[j]){
            i++;
            j++;
        } else {
            let k = from.indexOf(to[j]);
            if (k > i){
                remove(i, k - 1);
                i = k + 1;
                j++;
            } else {
                let l = to.indexOf(from[i]);
                if (l > j){
                    add(j, l - 1);
                    i++;
                    j = l + 1;
                }
            }
        }
    }

    if (i < totalFrom){
        remove(i, totalFrom - 1);
    }

    if (j < totalTo){
        add(j, totalTo - 1);
    }
}

let a = [1,2,3,4,5];
let b = [1,3,2,4,5,6,7];
diff(a, b, (from, to) => {
    console.log(`add: ${from} ~ ${to}`);
}, (from, to) => {
    console.log(`remove: ${from} ~ ${to}`);
});

上述测试代码得到的log感觉没啥问题。

remove: 1 ~ 1
add: 2 ~ 2
add: 5 ~ 6

修改dijest

原来的dijest中,我们是比较length来判定list是否发生改变的,现在需要改为diff。

dijest.js

/**
 * dijest a watcher, recursively
 */
const _dijest = (watcher) => {
    if (watcher.val){
        let newV = watcher.val();
        if (watcher.isModel){
            watcher.update(watcher.oldV, newV || '');
            watcher.oldV = newV;
        } else if (!watcher.isArray && (watcher.oldV !== newV)){
            console.log(`dijest: ${watcher.expression}, ${watcher.oldV} => ${newV}`);
            watcher.update(watcher.oldV, newV);
            watcher.oldV = newV;
        } else if (watcher.isArray){
            let oldV = watcher.oldV || [];
            diff(oldV, newV, watcher.update.add, watcher.update.remove)
            watcher.oldV = newV.slice(0);
        }
    }

    if (watcher.childs){
        watcher.childs.forEach(_dijest);
    }
};

由于diff中需要传入add和delete方法,bindNode中的update也需要更改,暂且假设update包含add和remove两个方法。 注意由于业务逻辑中是直接操纵的数组,所以在dijest中需要保存数组之前的结果,这个由于数组中存放的实际上是对象的引用,所以不会占用太多的资源。

bindNode.js

case 'for':
    newWatcher = {
        expression: parsed.expression,
        isArray: true,
        val: parsed.update.bind(null, scope),
        update: {
            add: (arr, from, to) => {
                console.log('update add', from, to);
                let endAnchor = extra.forAnchorEnd;
                let parentNode = endAnchor.parentNode;
                let tmpl = extra.tmpl;
                let i = from;
                while (i <= to){
                    let newNode = tmpl.cloneNode('deep');
                    parseConfig.replacement = {
                        from: extra.itemExpression,
                        to: parsed.expression.replace('scope.', '') + '[' + i + ']'
                    };
                    parseDom(newNode, scope, newWatcher);
                    parentNode.insertBefore(newNode, parentNode.childNodes[to]);
                    i++;
                }
            },

            remove: (arr, from, to) => {
                console.log('update remove', from, to);
                let endAnchor = extra.forAnchorEnd;
                let parentNode = endAnchor.parentNode;
                let i = from;
                let target = endAnchor.parentNode.childNodes[i];
                while (i <= to){
                    target = target.nextSibling;
                    parentNode.removeChild(target);
                    i++;
                }
            }
        }
    };
    break;

这里面没有复杂的逻辑,提供addremove两个方法,然后更新dom即可。

watcher的调整

这里比较复杂一点,目前的代码的效果和之前并无二致,因为都是将dom更新到合适的数量而已。而关键在于对child watcher的处理。

比如如果有三个元素的时候,根据文章最开始的介绍,应该会有scope.todos[0].name, scope.todos[1].name,scope.todos[2].name这三个child watcher,watcher是如下结构:

{
    expression,
    oldV,
    parent,
    update(oldV, newV),
    val()
}

其中目标dom是以闭包的形式包含在update()中,而值的计算也是闭包的形式包含在val()中的,这导致update的目标node无法更改。比如第二个元素被删除的时候,第三个元素变成第二个元素,原来的第三个watcher被unwatch掉,而第二个watcher被触发,但是原来的node已经删掉了,报错。

综上所述,watcher中需要有一个可以更改的node字段,现在开始修改bindNode()

bindNode.js

const bindNode = (node, type, scope, parsed, extra) => {
    let parentWatcher = extra.parentWatcher || watchers;
    let newWatcher = null;
    switch (type) {
    case 'text':
        newWatcher = {
            node,
            expression: parsed.expression,
            val: parsed.update.bind(null, scope),
            update(oldV, newV){
                this.node.textContent = newV
            }
        };
        break;
    case 'attr':
        newWatcher = {
            node,
            expression: parsed.expression,
            val: parsed.update.bind(null, scope),
            update(oldV, newV){
                this.node.setAttribute(extra.name, newV);
            }
        };
        break;
    case 'style':
        newWatcher = {
            node,
            expression: parsed.expression,
            val: parsed.update.bind(null, scope),
            update(oldV, newV){
                setStyle(this.node, newV)
            }
        };
        break;
    case 'value':
        newWatcher = {
            node,
            expression: parsed.expression,
            val: parsed.update.bind(null, scope),
            update(oldV, newV){
                this.node.value = newV;
            },
            isModel: true
        };
        break;
    case 'for':

在for的remove处理中,对剩下的listener进行如下调整。

case 'for':
    newWatcher = {
        expression: parsed.expression,
        isArray: true,
        val: parsed.update.bind(null, scope),
        update: {
            add: (arr, from, to) => {
                console.log('update add', from, to);
                let endAnchor = extra.forAnchorEnd;
                let parentNode = endAnchor.parentNode;
                let tmpl = extra.tmpl;
                let i = from;
                while (i <= to){
                    let newNode = tmpl.cloneNode('deep');
                    parseConfig.replacement = {
                        from: extra.itemExpression,
                        to: parsed.expression.replace('scope.', '') + '[' + i + ']'
                    };
                    parseDom(newNode, scope, newWatcher);
                    parentNode.insertBefore(newNode, parentNode.childNodes[to]);
                    i++;
                }
            },

            remove: (arr, from, to) => {
                console.log('update remove', from, to);
                let endAnchor = extra.forAnchorEnd;
                let parentNode = endAnchor.parentNode;
                let i = from;
                let target = endAnchor.parentNode.childNodes[i];
                let total =  newWatcher.childs.length

                // update child watchers
                while(i < total - to + from - 1){
                    newWatcher.childs[i].node = newWatcher.childs[i + to - from + 1].node;
                    newWatcher.childs[i].oldV = newWatcher.childs[i + to - from + 1].oldV;
                    i++;
                }

                // delete dom
                i = from;
                while (i <= to){
                    parentNode.removeChild(target);
                    target = target.nextSibling;
                    i++;
                }

                // unwatch child watchers
                i = 0;
                let childWatchers = newWatcher.childs;
                while (i < to - from + 1){
                    unwatch(childWatchers[childWatchers.length - 1]);
                    i++;
                }
            }
        }
    };
    break;

测试

可以在console或者chrome inspect中看到不再像以前产生多余的dom操作了,给自己点个赞。

本次代码已经commit到github,有兴趣的同学可以在那里查看。 在下一篇文章中,我们将尝试完成一个非常重要的概念-Component,啊,不对,在Angular 1.x中它叫directive。敬请期待w