Hatena::ブログ(Diary)

IT戦記 このページをアンテナに追加 RSSフィード Twitter

2009-09-24

live な NodeList の作り方

live な NodeList 概要

NodeList の IDL
interface NodeList {
    Node               item(in unsigned long index);
    readonly attribute unsigned long    length;
};
Interface NodeList - Document Object Model Core
「live な」NodeList とは

DOM の変更が動的に反映される NodeList のこと

現状の leve な NodeList のユースケース
  • getElementsByTagName
  • getElementsByTagNameNS
  • getElementsByName
  • getElementsByClassName
  • childNodes
  • children, all, tags (IE legacy)

重要な事

現状の live な NodeList で取得出来るノードには以下のような特徴がある

  • NodeList の取得元のノードから子孫としてたどれる
  • ノードが持つプロパティを見れば、そのノードが NodeList に含まれるかが分かる(別のノードを意識する必要がない)

どのように実装すれば良いか

上にあげた特徴から

  • DOM ノードを走査する
  • 条件に当てはまる何番目かの要素を返す

だけで実装できることがわかる

JavaScript で書いてみる

ここから先は、書いてみているだけなので動作確認はしていない。typo とかで動かないかも

まずはシンプルに
function LiveNodeList(context, match) {
    this.context = context;
    this.match = match;
}

LiveNodeList.prototype.traverse = function traverse(node, process) {
    for (node = node.firstChild; node; node = node.nextSibling) {
        if (process.call(this, node)) return true;
        if (traverse.call(this, node, process)) return true;
    }
    return false;
};

LiveNodeList.prototype.item = function(i) {
    var result = undefined;
    this.traverse(this.context, function(node) {
        if (this.match(node)) {
            if (i == 0) {
                result = node;
                return true;
            }
            i--;
        }
        return false
    });
    return result;
};

LiveNodeList.prototype.length = function() {
    var i = 0;
    this.traverse(this.context, function(node) {
        if (this.match(node)) {
            i++;
        }
        return false;
    });
    return i;
};
これを使うと getElementsByTagName は以下のように実装出来る
Element.prototype.getElementsByTagName = function(tagName) {
    return new LiveNodeList(this, function(node) {
        return  node.hasOwnProperty('tagName') &&
                node.tagName.toLowerCase() == tagName.toLowerCase()
    });
};
item のマイナス値を考慮

item 関数はマイナス値も扱う事ができるので、それに対応する

function LiveNodeList(context, match) {
    this.context = context;
    this.match = match;
}

LiveNodeList.prototype.traverse = function traverse(node, firstProp, nextProp, process) {
    for (node = node[firstProp]; node; node = node[nextProp]) {
        if (process.call(this, node)) return true;
        if (traverse.call(this, node, process)) return true;
    }
    return false;
};

LiveNodeList.prototype.item = function(i) {
    var result = undefined;
    if (i >= 0) {
        var firstProp = 'firstChild';
        var nextProp = 'nextSibling';
    }
    else {
        i = - i - 1;
        var firstProp = 'lastChild';
        var nextProp = 'previousSibling';
    }
    this.traverse(this.context, firstProp, nextProp, function(node) {
        if (this.match(node)) {
            if (i == 0) {
                result = node;
                return true;
            }
            i--;
        }
        return false
    });
    return result;
};

LiveNodeList.prototype.length = function() {
    var i = 0;
    this.traverse(this.context, 'firstChild', 'nextSibling', function(node) {
        if (this.match(node)) {
            i++;
        }
        return false;
    });
    return i;
};
childNodes などの問題点

以下のようにすれば、 childNodes でもこの枠組みを使えるが、深くノードを走査をするのは無駄である

Element.prototype.childNodes = function() {
    var parent = this;
    return new LiveNodeList(this, function(node) {
        return node.parentNode == parent;
    });
};
走査する範囲を(子孫か子か)指定出来るようにする
function LiveNodeList(context, traverseDecsendant, match) {
    this.context = context;
    this.match = match;
    this.traverseDecsendant = traverseDecsendant;
}

LiveNodeList.prototype.traverse = function traverse(node, firstProp, nextProp, process) {
    for (node = node[firstProp]; node; node = node[nextProp]) {
        if (process.call(this, node)) return true;
        if (ths.traverseDecsendant && traverse.call(this, node, process)) return true;
    }
    return false;
};

// snip
キャッシュを効かす

DOMSubtreeModified イベントを使うのでここ以降の実装は UA によっては動かない

function LiveNodeList(context, traverseDecsendant, match) {
    var self = this;
    context.addEventListener('DOMSubtreeModified', function() { self.cache = null; }, false);

    this.cache = null;
    this.context = context;
    this.match = match;
    this.traverseDecsendant = traverseDecsendant;
}

LiveNodeList.prototype.traverse = function traverse(node, firstProp, nextProp, process) {
    for (node = node[firstProp]; node; node = node[nextProp]) {
        if (process.call(this, node)) return true;
        if (ths.traverseDecsendant && traverse.call(this, node, process)) return true;
    }
    return false;
};

LiveNodeList.prototype.item = function(i) {
    if (this.cache && this.cache.hasOwnProperty(i)) {
        return this.cache[i];
    }

    this.cache = this.cache || {};

    var result = undefined;
    if (i >= 0) {
        var firstProp = 'firstChild';
        var nextProp = 'nextSibling';
        var reverse = false;
    }
    else {
        i = - (i + 1);
        var firstProp = 'lastChild';
        var nextProp = 'previousSibling';
        var reverse = true;
    }

    var count = 0;
    this.traverse(this.context, firstProp, nextProp, function(node) {
        if (this.match(node)) {
            if (reverse) {
                this.cache[- count - 1] = node;
                if (this.cache.hasOwnProperty('length')) {
                    this.cache[this.cache.length - count - 1] = node;
                }
            }
            else {
                this.cache[count] = node;
                if (this.cache.hasOwnProperty('length')) {
                    this.cache[count - this.cache.length] = node;
                }
            }
            if (i == count) {
                result = node;
                return true;
            }
            count++;
        }
        return false
    });
    return result;
};

LiveNodeList.prototype.length = function() {
    if (this.cache && this.cache.hasOwnProperty('length')) {
        return this.cache.length;
    }

    this.cache = this.cache || {};

    var i = 0;
    this.traverse(this.context, 'firstChild', 'nextSibling', function(node) {
        if (this.match(node)) {
            this.cache[i] = node;
            i++;
        }
        return false;
    });

    this.cache.length = i;

    for (var j = 0; j < i; j++) {
        this.cache[j - i] = this.cache[j];
    }

    return i;
};

こんな感じで

割とシンプルに実装出来る

たぶん、 Selectors API が static な NodeList を採用しているのはこのようにシンプルに実装出来ないからだと思う