function TreeConstructor() {
    this.tokenStream = null;
    this.tokenStreamPos = 0;
    this.insertionMode = insertionMode_InitialPhase;
    this.document = document.implementation.createDocument('', '', null);
    this.openStack = [];
    this.activeList = [];
    this.headElement = null;
    this.formElement = null;
    this.fostering = 0;
    this.createElementsInNS = false;
}

TreeConstructor.prototype.construct = function (tokens) {
    this.tokenStream = tokens;
    this.run();
    return this.document;
}

TreeConstructor.prototype.popCurrentNode = function () { this.openStack.pop(); }
TreeConstructor.prototype.addToActiveList = function (e) { this.activeList.push(e); }

TreeConstructor.prototype.parseError = function (err) { debug("Parse error: " + err); }

TreeConstructor.prototype.currentNodeHasName = function (n) { return this.openStack[this.openStack.length-1].localName == n; }
TreeConstructor.prototype.nodeBeforeCurrentHasName = function (n) { return this.openStack[this.openStack.length-2].localName == n; }

TreeConstructor.prototype.popUntilOneOf = function (ns) {
    while (true) {
        var e = this.openStack.pop();
        for (var i = 0; i < ns.length; ++i)
            if (ns[i] === e.localName)
                return;
    }
}

TreeConstructor.prototype.clearActiveListUpToMarker = function () {
    for (var i = this.activeList.length-1; i >= 0; --i)
        if (this.activeList[i] === null)
            break;
    this.activeList.splice(i, this.activeList.length-i);
}

TreeConstructor.prototype.setInsertionMode = function (mode) {
    this.insertionMode = mode;
}

TreeConstructor.prototype.reprocessAsIf = function (token, mode) {
    this.processToken(token, mode);
}

TreeConstructor.prototype.reprocessWithFosteringAsIf = function (token, mode) {
    ++this.fostering;
    this.reprocessAsIf(token, mode);
    --this.fostering;
}

TreeConstructor.prototype.hasElementInScope = function (table, names) {
    var n = this.openStack.length-1;
    while (true) {
        var name = this.openStack[n].localName;
        for (var i = 0; i < names.length; ++i)
            if (name == names[i])
                return true;
        if (name == 'table') return false;
        if (! table && (name == 'caption' || name == 'td' || name == 'th' || name == 'button' || name == 'marquee' || name == 'object')) return false;
        if (name == 'html') return false;
        --n;
    }
}

TreeConstructor.prototype.hasElementObjectInScope = function (target) {
    var n = this.openStack.length-1;
    while (true) {
        if (this.openStack[n] === target) return true;
        var name = this.openStack[n].localName;
        if (name == 'table') return false;
        if (name == 'caption' || name == 'td' || name == 'th' || name == 'button' || name == 'marquee' || name == 'object') return false;
        if (name == 'html') return false;
        --n;
    }
}

TreeConstructor.prototype.activeListContainsA = function () {
    for (var i = this.activeList.length-1; i >= 0; --i) {
        if (this.activeList[i] === null) return false;
        if (this.activeList[i].localName === 'a') return true;
    }
    return false;
}

TreeConstructor.prototype.removeThatAElement = function () {
    for (var i = this.activeList.length-1; i >= 0; --i) {
        if (this.activeList[i] === null) return false;
        if (this.activeList[i].localName === 'a') {
            var n = this.activeList[i];
            this.activeList.splice(i, 1);
            for (var j = this.openStack.length-1; j >= 0; --j) {
                if (this.openStack[j] === n) {
                    this.openStack.splice(j, 1);
                    break;
                }
            }
            break;
        }
    }
}

TreeConstructor.prototype.ImpliedEndTagElements = { 'dd':1, 'dt':1, 'li':1, 'p':1, 'tbody':1, 'td':1, 'tfoot':1, 'th':1, 'thead':1, 'tr':1 };
TreeConstructor.prototype.generateImpliedEndTags = function (except) {
    while (1) {
        var name = this.openStack[this.openStack.length-1].localName;
        for (var i = 0; i < except.length; ++i)
            if (name == except[i]) return;
        if (this.ImpliedEndTagElements[name])
            this.processToken(['EndTag', name], this.insertionMode);
        else
            return;
    }
}

TreeConstructor.prototype.reconstructActiveFormattingElements = function () {
    if (this.activeList.length == 0) return;

    var n = this.activeList.length-1;
    var entry = this.activeList[n];
    if (entry === null) return;
    for (var i = this.openStack.length-1; i >= 0; --i) // search backwards for maybe efficiency
        if (this.openStack[i] === entry)
            return;

    while (n > 0) {
        --n;
        entry = this.activeList[n];
        if (entry === null) { ++n; break; }
        for (var i = this.openStack.length-1; i >= 0; --i)
            if (this.openStack[i] === entry)
                { ++n; break; }
    }
    while (n < this.activeList.length) {
        entry = this.activeList[n];
        var clone = entry.cloneNode(false);
        this.appendToCurrentNode(clone);
        this.openStack.push(clone);
        this.activeList[n] = clone;
        ++n;
    }
}

TreeConstructor.prototype.adoptionAgency = function (token) {
    while (1) {
//     for (var loop = 0; loop < 16; ++loop) {
// debug("@ stack = "+uneval(this.openStack.map(function(n){return n.localName})));
// debug("@ list = "+uneval(this.activeList.map(function(n){return n.localName})));
        var fmt;
        for (var fmt_listOff = this.activeList.length-1; ; --fmt_listOff) {
            fmt = this.activeList[fmt_listOff];
            if (! fmt) { // (reached marker (null), or fell off end of list (undefined))
                this.parseError("closed formatting element that wasn't active");
                return;
            } else if (fmt.localName === token[1]) {
                break;
            }
        }
// debug("@ fmt = "+fmt.localName);
// debug("@ fmt_listOff = "+fmt_listOff);
        // Find fmt in the open stack
        for (var fmt_stackOff = this.openStack.length-1; fmt_stackOff >= 0; --fmt_stackOff)
            if (this.openStack[fmt_stackOff] === fmt)
                break;
        // fmt not in stack
        if (fmt_stackOff < 0) {
            this.parseError("closed formatting element that wasn't open");
            this.activeList.splice(fmt_listOff, 1);
            return;
        }
        // fmt in stack but not in scope
        if (! this.hasElementObjectInScope(fmt)) {
            this.parseError("closed formatting element that wasn't in scope");
            return;
        }
// debug("@ fmt_stackOff = "+fmt_stackOff);

        var furthest_stackOff = null, furthest = null;
        for (var i = fmt_stackOff+1; i < this.openStack.length; ++i) {
            if (this.IsScoping[this.openStack[i].localName] || this.IsSpecial[this.openStack[i].localName]) { // !(formatting || phrasing) == (scoping || special)
                furthest_stackOff = i;
                furthest = this.openStack[i];
                break;
            }
        }
        if (! furthest) {
            this.openStack.splice(fmt_stackOff, this.openStack.length - fmt_stackOff);
            this.activeList.splice(fmt_listOff, 1);
            return;
        }
// debug("@ furthest = "+furthest.localName);
// debug("@ furthest_stackOff = "+furthest_stackOff);

        var common = this.openStack[fmt_stackOff-1];
        if (furthest.parentNode) furthest.parentNode.removeChild(furthest);
        var bookmark = fmt_listOff;

// debug("@ common = "+common.localName);

        var node_stackOff = furthest_stackOff, lastNode_stackOff = furthest_stackOff;
        while (1) {
            var node_listOff;
            // Remove inactive items
            while (1) {
                --node_stackOff;
                for (node_listOff = this.activeList.length-1; node_listOff >= 0; --node_listOff)
                    if (this.activeList[node_listOff] === this.openStack[node_stackOff])
                        break;
                if (node_listOff < 0)
                    this.openStack.splice(node_stackOff, 1);
                else
                    break;
            }
            if (node_stackOff == fmt_stackOff) break;
            if (lastNode_stackOff == furthest_stackOff) bookmark = node_listOff;
            var node = this.openStack[node_stackOff];
            if (node.childNodes.length) {
                var clone = node.cloneNode(false);
                this.openStack[node_stackOff] = clone;
                this.activeList[node_listOff] = clone;
                node = clone;
            }
            this.appendToElement(this.openStack[lastNode_stackOff], node);
            lastNode_stackOff = node_stackOff;
        }
        this.appendToElement(this.openStack[lastNode_stackOff], common);
        var clone = fmt.cloneNode(false);
        while (furthest.firstChild)
            clone.appendChild(furthest.firstChild);
        this.appendToElement(clone, furthest);
        this.activeList.splice(bookmark+1, 0, clone);
        this.activeList.splice(fmt_listOff, 1); // (bookmark >= fmt_listOff, so this should be safe)
        this.openStack.splice(furthest_stackOff+1, 0, clone);
        this.openStack.splice(fmt_stackOff, 1); // (furthest_stackOff > fmt_stackOff, so this should be safe)
    }
}

TreeConstructor.prototype.applyEndTag = function (token) {
    for (var i = this.openStack.length-1; i >= 0; --i) {
        var node = this.openStack[i];
        if (node.localName === token[1]) {
            this.generateImpliedEndTags([]);
            if (this.openStack[this.openStack.length-1].localName !== token[1])
                this.parseError("invalid end tag");
            this.openStack.splice(i, this.openStack.length-i);
            return;
        }
        if (! (this.IsScoping[node.localName] || this.IsSpecial[node.localName])) { // !(formatting || phrasing) == (scoping || special)
            this.parseError("invalid end tag ignored");
            return;
        }
    }
}

TreeConstructor.prototype.clearStackToContext = function (names) {
    for (var i = this.openStack.length-1; i >= 0; --i) {
        var node = this.openStack[i];
        var is = false;
        for (var j = 0; j < names.length; ++j)
            if (node.localName === names[j])
                is = true;
        if (is)
            break;
    }
    if (i != this.openStack.length-1) {
        this.parseError("found open elements when clearing to table context");
        this.openStack.splice(i+1, this.openStack.length - (i+1));
    }
}

TreeConstructor.prototype.FosteringNodes = { table:1, tbody:1, tfoot:1, thead:1, tr:1 };

TreeConstructor.prototype.appendToCurrentNode = function (e) {
    if (! this.fostering || ! this.FosteringNodes[this.openStack[this.openStack.length-1].localName]) {
        this.openStack[this.openStack.length-1].appendChild(e);
    } else {
        var fosterParent, parentedTable = null;
        for (var i = this.openStack.length-1; i >= 0; --i) {
            if (this.openStack[i].localName == 'table') {
                fosterParent = this.openStack[i].parentNode;
                if (fosterParent && fosterParent.nodeType == fosterParent.ELEMENT_NODE)
                    parentedTable = this.openStack[i];
                else
                    fosterParent = this.openStack[i-1];
                break;
            }
        }
        if (i < 0) fosterParent = this.openStack[0];
        if (parentedTable)
            fosterParent.insertBefore(e, parentedTable);
        else
            fosterParent.appendChild(e);
    }
}

TreeConstructor.prototype.appendToElement = function (e, tgt) {
    if (tgt === this.openStack[this.openStack.length-1])
        this.appendToCurrentNode(e);
    else
        tgt.appendChild(e);
}

TreeConstructor.prototype.insertElement = function (token) {
    var name = token[1];
    var e;
    if (this.createElementsInNS) {
        if (! name.match(/^[a-zA-Z_][a-zA-Z0-9_.-]*$/)) { // subset of XML Name
            name = '_INVALID-'+name.replace(/([^a-zA-Z_])/g, function (c) { return '.'+c.charCodeAt(0).toString(16) });
        }
        e = this.document.createElementNS('http://www.w3.org/1999/xhtml', name);
    } else {
        try {
            e = this.document.createElement(name);
        } catch (err) {
            name = '_INVALID-'+name.replace(/([^a-zA-Z_])/g, function (c) { return '.'+c.charCodeAt(0).toString(16) });
            e = this.document.createElement(name);
        }
    }

    for (var i = 0; i < token[2].length; ++i) {
        name = token[2][i][0];
        try {
            e.setAttribute(name, token[2][i][1]);
        } catch (err) {
            name = '_INVALID-'+name.replace(/([^a-zA-Z_])/g, function (c) { return '.'+c.charCodeAt(0).toString(16) });
            e.setAttribute(name, token[2][i][1]);
        }
    }
    this.appendToCurrentNode(e);
    this.openStack.push(e);
    return e;
}

TreeConstructor.prototype.insertHTMLElement = function () {
    var e;
    if (this.createElementsInNS)
        e = this.document.createElementNS('http://www.w3.org/1999/xhtml', 'html');
    else
        e = this.document.createElement('html');
    this.document.appendChild(e);
    this.openStack.push(e);
}

TreeConstructor.prototype.appendCharacterToCurrentNode = function (token) {
    if (! this.fostering || ! this.FosteringNodes[this.openStack[this.openStack.length-1].localName]) {
        var c = this.openStack[this.openStack.length-1];
        if (c.lastChild && c.lastChild.nodeType == c.TEXT_NODE)
            c.lastChild.data += token[1];
        else
            c.appendChild(this.document.createTextNode(token[1]));
    } else {
        var fosterParent, parentedTable = null;
        for (var i = this.openStack.length-1; i >= 0; --i) {
            if (this.openStack[i].localName == 'table') {
                fosterParent = this.openStack[i].parentNode;
                if (fosterParent && fosterParent.nodeType == fosterParent.ELEMENT_NODE)
                    parentedTable = this.openStack[i];
                else
                    fosterParent = this.openStack[i-1];
                break;
            }
        }
        if (i < 0) fosterParent = this.openStack[0];
        if (parentedTable) {
            if (parentedTable.previousSibling && parentedTable.previousSibling.nodeType == parentedTable.TEXT_NODE)
                parentedTable.previousSibling.data += token[1];
            else
                fosterParent.insertBefore(this.document.createTextNode(token[1]), parentedTable);
        } else {
            var c = fosterParent;
            if (c.lastChild && c.lastChild.nodeType == c.TEXT_NODE)
                c.lastChild.data += token[1];
            else
                c.appendChild(this.document.createTextNode(token[1]));
        }
    }
}

TreeConstructor.prototype.appendCommentToCurrentNode = function (token) {
    var c = this.document.createComment(token[1]);
    this.appendToCurrentNode(c);
}

TreeConstructor.prototype.appendCommentToDocument = function (token) {
    var c = this.document.createComment(token[1]);
    this.document.appendChild(c);
}

TreeConstructor.prototype.doDoctypeStuff = function (token) {
    // TODO: parse errors
    try {
        var d = this.document.implementation.createDocumentType(token[1], token[2] === null ? '' : token[2], token[3] === null ? '' : token[3]);
        this.document.appendChild(d);
    } catch (err) {
        var c = this.document.createComment('(pretend there\'s a doctype here)');
        this.document.appendChild(c);
    }
    // TODO: quirks
}

TreeConstructor.prototype.resetInsertionModeAppropriately = function () {
    var appropriate = { // TODO: make this a constant (but cope with inclusion ordering)
        select: insertionMode_MainPhase_InSelect,
        td: insertionMode_MainPhase_InCell,
        th: insertionMode_MainPhase_InCell,
        tr: insertionMode_MainPhase_InRow,
        tbody: insertionMode_MainPhase_InTableBody,
        thead: insertionMode_MainPhase_InTableBody,
        tfoot: insertionMode_MainPhase_InTableBody,
        caption: insertionMode_MainPhase_InCaption,
        colgroup: insertionMode_MainPhase_InColumnGroup,
        table: insertionMode_MainPhase_InTable,
        head: insertionMode_MainPhase_InBody,
        body: insertionMode_MainPhase_InBody,
        frameset: insertionMode_MainPhase_InFrameset
    };
    for (var i = this.openStack.length-1; i >= 0; --i) {
        var n = this.openStack[i].localName;
        // TODO: fragment stuff
        var m = appropriate[n];
        if (m) {
            this.setInsertionMode(m);
            return;
        }
        // TODO: fragment stuff
    }
    this.setInsertionMode(insertionMode_MainPhase_InBody);
}