var formatText = (function() {
    /** @type {string} */
    var text;

    /** @type {MsgBranch} */
    var root;

    var opts = {
        /** @type {Array<string>} */
        highlights: [],

        /** @type {function(string):string} */
        emojiFormatFunction: identity,

        /** @type {function(string):string} */
        textFilter: identity
    };

    /**
     * @constructor
     * @param {MsgBranch!} _parent
    **/
    function MsgTextLeaf(_parent) {
        /** @type {string} */
        this.text = "";

        /** @const @type {MsgBranch} */
        this._parent = _parent;
    }

    /**
     * @constructor
     * @param {MsgBranch} _parent
     * @param {number} triggerIndex
     * @param {string=} trigger
     */
    function MsgBranch(_parent, triggerIndex, trigger) {
        /** @const @type {number} */
        this.triggerIndex = triggerIndex;

        /** @type {MsgBranch|MsgTextLeaf|null} */
        this.lastNode = null;

        /** @type {Array<MsgBranch|MsgTextLeaf>} */
        this.subNodes = [ ];

        /** @const @type {string} */
        this.trigger = trigger || '';

        /** @type {boolean} */
        this.isLink = this.trigger === '<';

        /** @type {boolean} */
        this.isBold = this.trigger === '*';

        /** @type {boolean} */
        this.isItalic = this.trigger === '_';

        /** @type {boolean} */
        this.isStrike = this.trigger === '~' || this.trigger === '-';

        /** @type {boolean} */
        this.isQuote = this.trigger === '>' || this.trigger === "&gt;";

        /** @type {boolean} */
        this.isEmoji = this.trigger === ':';

        /** @type {boolean} */
        this.isCode = this.trigger === '`';

        /** @type {boolean} */
        this.isCodeBlock = this.trigger === '```';

        /** @type {boolean} */
        this.isEol = this.trigger === '\n';

        /** @type {boolean} */
        this.isHighlight = trigger !== undefined && opts.highlights.indexOf(trigger) !== -1;

        /** @const @type {MsgBranch} */
        this._parent = _parent;

        /** @type {MsgBranch|null} */
        this.prevTwin = null;

        /** @type {boolean|number} */
        this.terminated = this.isEol || this.isHighlight ? (triggerIndex +trigger.length -1) : false;

        if (this.isHighlight) {
            this.lastNode = new MsgTextLeaf(this);
            this.subNodes.push(this.lastNode);
            this.lastNode.text = /** @type {string} */ (trigger);
        }
    }

    /** @return {boolean} */
    MsgBranch.prototype.checkIsBold = function() {
        return (this.isBold && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsBold());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsItalic = function() {
        return (this.isItalic && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsItalic());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsStrike = function() {
        return (this.isStrike && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsStrike());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsQuote = function() {
        return (this.isQuote && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsQuote());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsEmoji = function() {
        return (this.isEmoji && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsEmoji());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsHighlight = function() {
        return (this.isHighlight && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsHighlight());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsCode = function() {
        return (this.isCode && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsCode());
    };

    /** @return {boolean} */
    MsgBranch.prototype.checkIsCodeBlock = function() {
        return (this.isCodeBlock && !!this.terminated) || (this._parent instanceof MsgBranch && this._parent.checkIsCodeBlock());
    };

    MsgBranch.prototype.containsUnterminatedBranch = function() {
        for (var i =0, nbBranches = this.subNodes.length; i < nbBranches; i++) {
            if (this.subNodes[i] instanceof MsgBranch && (
                    !this.subNodes[i].terminated || this.subNodes[i].containsUnterminatedBranch()))
                return true;
        }
        return false;
    };

    /**
     * Check if this token closes the branch
     * In this case, finishWith should return the new leave
     * Exemple: `_text *bold_ bold continue*` should be
     * + root
     * | italic
     *   | "text"
     *   | bold
     *     | "bold"
     * | bold
     *   | "bold continue"
     * and this function will return a "bold" branch
     *
     * @param {number} i
     * @return {boolean|MsgBranch}
    **/
    MsgBranch.prototype.finishWith = function(i) {
        var prevIsAlphadec = isAlphadec(text[i -1]);
        if (this.trigger === '<' && text[i] === '>' && prevIsAlphadec)
            return true;

        if (!this.isQuote && text.substr(i, this.trigger.length) === this.trigger) {
            if (!prevIsAlphadec && (this.isBold || this.isItalic || this.isStrike)) {
                // previous char is not compatible with finishing now
                return false;
            }
            if (this.lastNode && this.containsUnterminatedBranch()) // sub nodes contains at least one branch wich should be replicated
                return this.lastNode.makeNewBranchFromThis();
            else if (this.hasContent()) // self or any prevTwin has Content
                return true;
            // else no content, should not be finished now
        }
        if (text[i] === '\n' && this.isQuote)
            return true;
        return false;
    };

    /**
     * @return {boolean}
    **/
    MsgBranch.prototype.hasContent = function() {
        var _this = this;
        while (_this) {
            for (var i = 0, nbNodes = _this.subNodes.length; i < nbNodes; i++)
                if (_this.subNodes[i] instanceof MsgBranch || _this.subNodes[i].text.length)
                    return true;
            // self or any prevTwin has Content
            _this = _this.prevTwin;
        }
        return false;
    };

    /**
     * @return {MsgBranch}
    **/
    MsgBranch.prototype.makeNewBranchFromThis = function() {
        var other = new MsgBranch(this._parent, this.triggerIndex, this.trigger);
        other.prevTwin = this;
        if (this.lastNode && this.lastNode instanceof MsgBranch) {
            other.lastNode = this.lastNode.makeNewBranchFromThis();
            other.subNodes = [ other.lastNode ];
        }
        return other;
    };

    /**
     * Check if this token is compatible with this branch
     * @param {number} i
     * @return {boolean}
    **/
    MsgBranch.prototype.isAcceptable = function(i) {
        if (this.isEmoji && (text[i] === ' ' || text[i] === '\t'))
            return false;
        if ((this.isEmoji || this.isLink || this.isBold || this.isItalic || this.isStrike || this.isCode) && text[i] === '\n')
            return false;
        return true;
    };

    /**
     * Check if str[i] is a trigger for a new node
     * if true, return the trigger
     * @param {number} i
     * @return {string|null}
    **/
    MsgBranch.prototype.isNewToken = function(i) {
        if (this.isCode || this.isEmoji || this.isCodeBlock)
            return null;
        var nextIsAlphadec = isAlphadec(text[i +1]);

        if (text.substr(i, 3) === '```')
            return '```';
        if (isBeginingOfLine()) {
            if (text.substr(i, 4) === "&gt;")
                return "&gt;";
            if (text[i] === '>')
                return text[i];
        }
        if (['`', '\n'].indexOf(text[i]) !== -1)
            return text[i];
        if (['*', '~', '-', '_' ].indexOf(text[i]) !== -1 && (nextIsAlphadec || ['*', '~', '-', '_', '<', '&'].indexOf(text[i+1]) !== -1))
            return text[i];
        if ([':', '<'].indexOf(text[i]) !== -1 && nextIsAlphadec)
            return text[i];

        for (var highlightIndex =0, nbHighlight =opts.highlights.length; highlightIndex < nbHighlight; highlightIndex++) {
            var highlight = opts.highlights[highlightIndex];

            // TODO compare with collators
            if (text.substr(i, highlight.length) === highlight)
                return highlight;
        }
        return null;
    };

    /** @return {boolean|undefined} */
    MsgTextLeaf.prototype.isBeginingOfLine = function() {
        if (this.text.trim() !== '')
            return false;
        return undefined;
    };

    /** @return {boolean|undefined} */
    MsgBranch.prototype.isBeginingOfLine = function() {
        for (var i = this.subNodes.length -1; i >= 0; i--) {
            var isNewLine = this.subNodes[i].isBeginingOfLine();
            if (isNewLine !== undefined)
                return isNewLine;
        }
        if (this.isEol || this.isQuote)
            return true;
        return undefined;
    };

    /**
     * @param {string} c
     * @return {boolean}
     **/
    function isAlphadec(c) {
        return ((c >= 'A' && c <= 'Z') ||
            (c >= 'a' && c <= 'z') ||
            (c >= '0' && c <= '9') ||
            "àèìòùÀÈÌÒÙáéíóúýÁÉÍÓÚÝâêîôûÂÊÎÔÛãñõÃÑÕäëïöüÿÄËÏÖÜŸçÇßØøÅåÆæœ".indexOf(c) !== -1);
    }

    /** @return {boolean} */
    function isBeginingOfLine() {
        var isNewLine = root.isBeginingOfLine();
        return isNewLine === undefined ? true : isNewLine;
    };

    /** @return {number} */
    MsgTextLeaf.prototype.addChar = function(i) {
        this.text += text[i];
        return 1;
    };

    /**
     * Parse next char
     * @param {number} i
     * @return {number}
    **/
    MsgBranch.prototype.addChar = function(i) {
        var isFinished = (this.lastNode && !this.lastNode.terminated && this.lastNode.finishWith) ? this.lastNode.finishWith(i) : null;

        if (isFinished) {
            var lastTriggerLen = this.lastNode.trigger.length;
            this.lastNode.terminate(i);
            if (isFinished instanceof MsgBranch) {
                this.lastNode = isFinished;
                this.subNodes.push(isFinished);
            }
            return lastTriggerLen;
        } else {
            if (!this.lastNode || this.lastNode.terminated || this.lastNode instanceof MsgTextLeaf || this.lastNode.isAcceptable(i)) {
                var isNewToken = this.isNewToken(i);
                if (isNewToken) {
                    // FIXME if this is a quote and newToken is also a quote, trim lastnode (and remove it if necessary)
                    this.lastNode = new MsgBranch(this, i, isNewToken);
                    this.subNodes.push(this.lastNode);
                    return this.lastNode.trigger.length;
                } else {
                    if (!this.lastNode || this.lastNode.terminated) {
                        this.lastNode = new MsgTextLeaf(this);
                        this.subNodes.push(this.lastNode);
                    }
                    return this.lastNode.addChar(i);
                }
            } else {
                // last branch child is not compatible with this token.
                // So, lastBranch is not a branch
                var revertTo = this.lastNode.triggerIndex +1;

                root.cancelTerminate(this.lastNode.triggerIndex);
                // Add a new "escaped" node to replace trigger
                this.lastNode = new MsgTextLeaf(this);
                this.lastNode.addChar(revertTo -1); // Add "escaped" trigger
                this.subNodes.pop();
                this.subNodes.push(this.lastNode);

                // return negative value to start parsing again
                return revertTo -i;
            }
        }
    };

    MsgBranch.prototype.terminate = function(terminateAtIndex) {
        var _this = this;
        while (_this) {
            _this.terminated = terminateAtIndex;
            _this = _this.prevTwin;
        }
    };

    /**
     * @param {number} unTerminatedIndex
    **/
    MsgBranch.prototype.cancelTerminate = function(unTerminatedIndex) {
        if (this.terminated && this.terminated >= unTerminatedIndex)
            this.terminated = false;
        this.subNodes.forEach(function(node) {
            if (node instanceof MsgBranch) {
                node.cancelTerminate(unTerminatedIndex);
            }
        });
    };

    /**
     * @return {string}
    **/
    MsgTextLeaf.prototype.innerHTML = function() {
        if (this._parent.checkIsEmoji()) {
            var _parent = this._parent;
            while (_parent && !_parent.isEmoji)
                _parent = _parent._parent;
            if (_parent)
                return opts.emojiFormatFunction(_parent.trigger +this.text +_parent.trigger);
            return opts.emojiFormatFunction(this.text);
        }
        if (this._parent.checkIsCodeBlock())
            return this.text.replace(/\n/g, '<br/>'); // TODO syntax highlight
        return opts.textFilter(this.text);
    };

    /**
     * @return {string}
    **/
    MsgTextLeaf.prototype.outerHTML = function() {
        var tagName = 'span'
            ,classList = [];

        if (this._parent.checkIsCodeBlock()) {
            classList.push('codeblock');
        } else if (this._parent.checkIsCode()) {
            classList.push('code');
        } else {
            if (this.isLink)
                tagName = 'a';
            if (this._parent.checkIsBold())
                classList.push('bold');
            if (this._parent.checkIsItalic())
                classList.push('italic');
            if (this._parent.checkIsStrike())
                classList.push('strike');
            if (this._parent.checkIsEmoji())
                classList.push('emoji');
            if (this._parent.checkIsHighlight())
                classList.push('highlight');
        }
        return '<' +tagName +(classList.length ? ' class="' +classList.join(' ') +'"' : '') +'>' +this.innerHTML() +'</' +tagName +'>';
    };

    MsgBranch.prototype.outerHTML = function() {
        var html = "";

        if (this.isQuote)
            html += '<span class="quote">';
        if (this.isEol)
            html += '<br/>';

        this.subNodes.forEach(function(node) {
            html += node.outerHTML();
        });

        if (this.isQuote)
            html += '</span>';
        return html;
    };

    /** @param {MsgBranch=} _root */
    function getFirstUnterminated(_root) {
        _root = _root || root;
        for (var i =0, nbBranches = _root.subNodes.length; i < nbBranches; i++) {
            var branch = _root.subNodes[i];

            if (branch instanceof MsgBranch) {
                if (!branch.terminated) {
                    return branch;
                } else {
                    var unTerminatedChild = getFirstUnterminated(branch);
                    if (unTerminatedChild)
                        return unTerminatedChild;
                }
            }
        }
        return null;
    };

    /**
     * @param {MsgBranch} branch
     * @param {boolean} next kill this branch or all the next ones ?
    **/
    function revertTree(branch, next) {
        if (branch._parent instanceof MsgBranch) {
            branch._parent.subNodes.splice(branch._parent.subNodes.indexOf(branch) +(next ? 1 : 0));
            branch._parent.lastNode = branch._parent.subNodes[branch._parent.subNodes.length -1];
            revertTree(branch._parent, true);
        }
    };

    MsgBranch.prototype.implicitClose = function(i) {
        if (this.isQuote && !this.terminated) {
            this.terminate(i);
        }
        this.subNodes.forEach(function(node) {
            if (node instanceof MsgBranch)
                node.implicitClose(i);
        });
    };

    /**
     * Try to close the tree.
     * If a problem is found, return its index after reverting tree at this position
     * @return {number|undefined}
    **/
    function eof() {
        root.implicitClose(text.length);
        var unterminated = getFirstUnterminated();

        if (unterminated) {
            // We have a first token, but never closed
            // kill that branch
            revertTree(unterminated, false);

            // "unterminate" all branch that will be closed in the future
            root.cancelTerminate(unterminated.triggerIndex);

            // Add a new text leaf containing trigger
            var textNode = new MsgTextLeaf(unterminated._parent);
            textNode.addChar(unterminated.triggerIndex);
            unterminated._parent.subNodes.push(textNode);
            unterminated._parent.lastNode = textNode;

            // Restart parsing
            return unterminated.triggerIndex +1;
        } else {
            // FIXME merge of same block-branches (opti)
        }
    };

    function identity(a) { return a; }

    /**
     * @param {string} _text
     * @param {({
         * highlights: (Array<string>|undefined),
         * emojiFormatFunction: (function(string):string|undefined),
         * textFilter: (function(string):string|undefined)
         * })=} _opts
     * @return {string}
    **/
    function _parse(_text, _opts) {
        if (!_opts)
            _opts = {};
        opts.highlights = _opts.highlights || [];
        opts.emojiFormatFunction = _opts.emojiFormatFunction || identity;
        opts.textFilter = _opts.textFilter || identity;
        text = _text;

        root = new MsgBranch(this, 0);
        var i =0,
            textLen = text.length;
        do {
            while (i < textLen)
                i += root.addChar(i);
            i = eof();
        } while (i !== undefined);

        return root.outerHTML();
    };
    return _parse;
})();

window['_formatText'] = function(str, opts) {
    return formatText(str, {
        highlights: opts ? opts["highlights"] : undefined
    });
}
if (typeof module !== "undefined") module.exports.formatText = formatText;