/**#@+
* Boolean rules bitfield
*/
/** @const */ var RULE_AUTO_CLOSE        = 1 << 0;
/** @const */ var RULE_AUTO_REOPEN       = 1 << 1;
/** @const */ var RULE_BREAK_PARAGRAPH   = 1 << 2;
/** @const */ var RULE_CREATE_PARAGRAPHS = 1 << 3;
/** @const */ var RULE_DISABLE_AUTO_BR   = 1 << 4;
/** @const */ var RULE_ENABLE_AUTO_BR    = 1 << 5;
/** @const */ var RULE_IGNORE_TAGS       = 1 << 6;
/** @const */ var RULE_IGNORE_TEXT       = 1 << 7;
/** @const */ var RULE_IGNORE_WHITESPACE = 1 << 8;
/** @const */ var RULE_IS_TRANSPARENT    = 1 << 9;
/** @const */ var RULE_PREVENT_BR        = 1 << 10;
/** @const */ var RULE_SUSPEND_AUTO_BR   = 1 << 11;
/** @const */ var RULE_TRIM_FIRST_LINE   = 1 << 12;
/**#@-*/

/**
* @const Bitwise disjunction of rules related to automatic line breaks
*/
var RULES_AUTO_LINEBREAKS = RULE_DISABLE_AUTO_BR | RULE_ENABLE_AUTO_BR | RULE_SUSPEND_AUTO_BR;

/**
* @const Bitwise disjunction of rules that are inherited by subcontexts
*/
var RULES_INHERITANCE = RULE_ENABLE_AUTO_BR;

/**
* @const All the characters that are considered whitespace
*/
var WHITESPACE = " \n\t";

/**
* @type {!Object.<string,number>} Number of open tags for each tag name
*/
var cntOpen;

/**
* @type {!Object.<string,number>} Number of times each tag has been used
*/
var cntTotal;

/**
* @type {!Object} Current context
*/
var context;

/**
* @type {number} How hard the parser has worked on fixing bad markup so far
*/
var currentFixingCost;

/**
* @type {?Tag} Current tag being processed
*/
var currentTag;

/**
* @type {boolean} Whether the output contains "rich" tags, IOW any tag that is not <p> or <br/>
*/
var isRich;

/**
* @type {!Logger} This parser's logger
*/
var logger = new Logger;

/**
* @type {number} How hard the parser should work on fixing bad markup
*/
var maxFixingCost = 10000;

/**
* @type {!Object} Associative array of namespace prefixes in use in document (prefixes used as key)
*/
var namespaces;

/**
* @type {!Array.<!Tag>} Stack of open tags (instances of Tag)
*/
var openTags;

/**
* @type {string} This parser's output
*/
var output;

/**
* @type {!Object.<!Object>}
*/
var plugins;

/**
* @type {number} Position of the cursor in the original text
*/
var pos;

/**
* @type {!Object} Variables registered for use in filters
*/
var registeredVars;

/**
* @type {!Object} Root context, used at the root of the document
*/
var rootContext;

/**
* @type {!Object} Tags' config
* @const
*/
var tagsConfig;

/**
* @type {!Array.<!Tag>} Tag storage
*/
var tagStack;

/**
* @type {boolean} Whether the tags in the stack are sorted
*/
var tagStackIsSorted;

/**
* @type {string} Text being parsed
*/
var text;

/**
* @type {number} Length of the text being parsed
*/
var textLen;

/**
* @type {number} Counter incremented everytime the parser is reset. Used to as a canary to detect
*                 whether the parser was reset during execution
*/
var uid = 0;

/**
* @type {number} Position before which we output text verbatim, without paragraphs or linebreaks
*/
var wsPos;

//==========================================================================
// Public API
//==========================================================================

/**
* Disable a tag
*
* @param {string} tagName Name of the tag
*/
function disableTag(tagName)
{
if (tagsConfig[tagName])
{
copyTagConfig(tagName).isDisabled = true;
}
}

/**
* Enable a tag
*
* @param {string} tagName Name of the tag
*/
function enableTag(tagName)
{
if (tagsConfig[tagName])
{
copyTagConfig(tagName).isDisabled = false;
}
}

/**
* Get this parser's Logger instance
*
* @return {!Logger}
*/
function getLogger()
{
return logger;
}

/**
* Parse a text
*
* @param  {string} _text Text to parse
* @return {string}       XML representation
*/
function parse(_text)
{
// Reset the parser and save the uid
reset(_text);
var _uid = uid;

// Do the heavy lifting
executePluginParsers();
processTags();

// Finalize the document
finalizeOutput();

// Check the uid in case a plugin or a filter reset the parser mid-execution
if (uid !== _uid)
{
throw 'The parser has been reset during execution';
}

// Log a warning if the fixing cost limit was exceeded
if (currentFixingCost > maxFixingCost)
{
logger.warn('Fixing cost limit exceeded');
}

return output;
}

/**
* Reset the parser for a new parsing
*
* @param {string} _text Text to be parsed
*/
function reset(_text)
{
// Normalize CR/CRLF to LF, remove control characters that aren't allowed in XML
_text = _text.replace(/\r\n?/g, "\n");
_text = _text.replace(/[\x00-\x08\x0B\x0C\x0E-\x1F]+/g, '');

// Clear the logs
logger.clear();

// Initialize the rest
cntOpen           = {};
cntTotal          = {};
currentFixingCost = 0;
currentTag        = null;
isRich            = false;
namespaces        = {};
openTags          = [];
output            = '';
pos               = 0;
tagStack          = [];
tagStackIsSorted  = false;
text              = _text;
textLen           = text.length;
wsPos             = 0;

// Initialize the root context
context = rootContext;
context.inParagraph = false;

// Bump the UID
++uid;
}

/**
* Change a tag's tagLimit
*
* NOTE: the default tagLimit should generally be set during configuration instead
*
* @param {string} tagName  The tag's name, in UPPERCASE
* @param {number} tagLimit
*/
function setTagLimit(tagName, tagLimit)
{
if (tagsConfig[tagName])
{
copyTagConfig(tagName).tagLimit = tagLimit;
}
}

/**
* Change a tag's nestingLimit
*
* NOTE: the default nestingLimit should generally be set during configuration instead
*
* @param {string} tagName      The tag's name, in UPPERCASE
* @param {number} nestingLimit
*/
function setNestingLimit(tagName, nestingLimit)
{
if (tagsConfig[tagName])
{
copyTagConfig(tagName).nestingLimit = nestingLimit;
}
}

/**
* Copy a tag's config
*
* This method ensures that the tag's config is its own object and not shared with another
* identical tag
*
* @param  {string} tagName Tag's name
* @return {!Object}         Tag's config
*/
function copyTagConfig(tagName)
{
var tagConfig = {}, k;
for (k in tagsConfig[tagName])
{
tagConfig[k] = tagsConfig[tagName][k];
}

return tagsConfig[tagName] = tagConfig;
}

//==========================================================================
// Output handling
//==========================================================================

/**
* Replace Unicode characters outside the BMP with XML entities in the output
*/
function encodeUnicodeSupplementaryCharacters()
{
output = output.replace(
/[\uD800-\uDBFF][\uDC00-\uDFFF]/g,
encodeUnicodeSupplementaryCharactersCallback
);
}

/**
* Encode given surrogate pair into an XML entity
*
* @param  {string} pair Surrogate pair
* @return {string}      XML entity
*/
function encodeUnicodeSupplementaryCharactersCallback(pair)
{
var cp = (pair.charCodeAt(0) << 10) + pair.charCodeAt(1) - 56613888;

return '&#' + cp + ';';
}

/**
* Finalize the output by appending the rest of the unprocessed text and create the root node
*/
function finalizeOutput()
{
var tmp;

// Output the rest of the text and close the last paragraph
outputText(textLen, 0, true);

// Remove empty tag pairs, e.g. <I><U></U></I> as well as empty paragraphs
do
{
tmp = output;
output = output.replace(/<([^ />]+)[^>]*><\/\1>/g, '');
}
while (output !== tmp);

// Merge consecutive <i> tags
output = output.replace(/<\/i><i>/g, '');

// Remove control characters from the output to ensure it's valid XML
output = output.replace(/[\x00-\x08\x0B-\x1F]/g, '');

// Encode Unicode characters that are outside of the BMP
encodeUnicodeSupplementaryCharacters();

// Use a <r> root if the text is rich, or <t> for plain text (including <p></p> and <br/>)
var tagName = (isRich) ? 'r' : 't';

// Prepare the root node with all the namespace declarations
tmp = '<' + tagName;
if (HINT.namespaces)
{
for (var prefix in namespaces)
{
tmp += ' xmlns:' + prefix + '="urn:s9e:TextFormatter:' + prefix + '"';
}
}

output = tmp + '>' + output + '</' + tagName + '>';
}

/**
* Append a tag to the output
*
* @param {!Tag} tag Tag to append
*/
function outputTag(tag)
{
isRich = true;

var tagName    = tag.getName(),
tagPos     = tag.getPos(),
tagLen     = tag.getLen(),
tagFlags   = tag.getFlags(),
skipBefore = 0,
skipAfter  = 0;

if (HINT.RULE_IGNORE_WHITESPACE && (tagFlags & RULE_IGNORE_WHITESPACE))
{
skipBefore = 1;
skipAfter  = (tag.isEndTag()) ? 2 : 1;
}

// Current paragraph must end before the tag if:
//  - the tag is a start (or self-closing) tag and it breaks paragraphs, or
//  - the tag is an end tag (but not self-closing)
var closeParagraph = !!(!tag.isStartTag() || (HINT.RULE_BREAK_PARAGRAPH && (tagFlags & RULE_BREAK_PARAGRAPH)));

// Let the cursor catch up with this tag's position
outputText(tagPos, skipBefore, closeParagraph);

// Capture the text consumed by the tag
var tagText = (tagLen)
? htmlspecialchars_noquotes(text.substring(tagPos, tagPos + tagLen))
: '';

// Output current tag
if (tag.isStartTag())
{
// Handle paragraphs before opening the tag
if (!HINT.RULE_BREAK_PARAGRAPH || !(tagFlags & RULE_BREAK_PARAGRAPH))
{
outputParagraphStart(tagPos);
}

// Record this tag's namespace, if applicable
if (HINT.namespaces)
{
var colonPos = tagName.indexOf(':');
if (colonPos > 0)
{
namespaces[tagName.substring(0, colonPos)] = 0;
}
}

// Open the start tag and add its attributes, but don't close the tag
output += '<' + tagName;

// We output the attributes in lexical order. Helps canonicalizing the output and could
// prove useful someday
var attributes = tag.getAttributes(),
attributeNames = [];
for (var attrName in attributes)
{
attributeNames.push(attrName);
}
attributeNames.sort(
function(a, b)
{
return (a > b) ? 1 : -1;
}
);
attributeNames.forEach(
function(attrName)
{
output += ' ' + attrName + '="' + htmlspecialchars_compat(attributes[attrName].toString()).replace(/\n/g, '&#10;') + '"';
}
);

if (tag.isSelfClosingTag())
{
if (tagLen)
{
output += '>' + tagText + '</' + tagName + '>';
}
else
{
output += '/>';
}
}
else if (tagLen)
{
output += '><s>' + tagText + '</s>';
}
else
{
output += '>';
}
}
else
{
if (tagLen)
{
output += '<e>' + tagText + '</e>';
}

output += '</' + tagName + '>';
}

// Move the cursor past the tag
pos = tagPos + tagLen;

// Skip newlines (no other whitespace) after this tag
wsPos = pos;
while (skipAfter && wsPos < textLen && text[wsPos] === "\n")
{
// Decrement the number of lines to skip
--skipAfter;

// Move the cursor past the newline
++wsPos;
}
}

/**
* Output the text between the cursor's position (included) and given position (not included)
*
* @param  {number}  catchupPos     Position we're catching up to
* @param  {number}  maxLines       Maximum number of lines to ignore at the end of the text
* @param  {boolean} closeParagraph Whether to close the paragraph at the end, if applicable
*/
function outputText(catchupPos, maxLines, closeParagraph)
{
if (closeParagraph)
{
if (!(context.flags & RULE_CREATE_PARAGRAPHS))
{
closeParagraph = false;
}
else
{
// Ignore any number of lines at the end if we're closing a paragraph
maxLines = -1;
}
}

if (pos >= catchupPos)
{
// We're already there, close the paragraph if applicable and return
if (closeParagraph)
{
outputParagraphEnd();
}
}

// Skip over previously identified whitespace if applicable
if (wsPos > pos)
{
var skipPos = Math.min(catchupPos, wsPos);
output += text.substring(pos, skipPos);
pos = skipPos;

if (pos >= catchupPos)
{
// Skipped everything. Close the paragraph if applicable and return
if (closeParagraph)
{
outputParagraphEnd();
}
}
}

var catchupText;

// Test whether we're even supposed to output anything
if (HINT.RULE_IGNORE_TEXT && context.flags & RULE_IGNORE_TEXT)
{
catchupText = text.substring(pos, catchupPos);

// If the catchup text is not entirely composed of whitespace, we put it inside ignore tags
if (!/^[ \n\t]*$/.test(catchupText))
{
catchupText = '<i>' + htmlspecialchars_noquotes(catchupText) + '</i>';
}

output += catchupText;
pos = catchupPos;

if (closeParagraph)
{
outputParagraphEnd();
}

return;
}

// Compute the amount of text to ignore at the end of the output
var ignorePos = catchupPos,
ignoreLen = 0;

// Ignore as many lines (including whitespace) as specified
while (maxLines && --ignorePos >= pos)
{
var c = text[ignorePos];
if (c !== ' ' && c !== "\n" && c !== "\t")
{
break;
}

if (c === "\n")
{
--maxLines;
}

++ignoreLen;
}

// Adjust catchupPos to ignore the text at the end
catchupPos -= ignoreLen;

// Break down the text in paragraphs if applicable
if (HINT.RULE_CREATE_PARAGRAPHS && context.flags & RULE_CREATE_PARAGRAPHS)
{
if (!context.inParagraph)
{
outputWhitespace(catchupPos);

if (catchupPos > pos)
{
outputParagraphStart(catchupPos);
}
}

// Look for a paragraph break in this text
var pbPos = text.indexOf("\n\n", pos);

while (pbPos > -1 && pbPos < catchupPos)
{
outputText(pbPos, 0, true);
outputParagraphStart(catchupPos);

pbPos = text.indexOf("\n\n", pos);
}
}

// Capture, escape and output the text
if (catchupPos > pos)
{
catchupText = htmlspecialchars_noquotes(
text.substring(pos, catchupPos)
);

// Format line breaks if applicable
if (HINT.RULE_ENABLE_AUTO_BR && (context.flags & RULES_AUTO_LINEBREAKS) === RULE_ENABLE_AUTO_BR)
{
catchupText = catchupText.replace(/\n/g, "<br/>\n");
}

output += catchupText;
}

// Close the paragraph if applicable
if (closeParagraph)
{
outputParagraphEnd();
}

// Add the ignored text if applicable
if (ignoreLen)
{
output += text.substring(catchupPos, catchupPos + ignoreLen);
}

// Move the cursor past the text
pos = catchupPos + ignoreLen;
}

/**
* Output a linebreak tag
*
* @param {!Tag} tag
*/
function outputBrTag(tag)
{
outputText(tag.getPos(), 0, false);
output += '<br/>';
}

/**
* Output an ignore tag
*
* @param {!Tag} tag
*/
function outputIgnoreTag(tag)
{
var tagPos = tag.getPos(),
tagLen = tag.getLen();

// Capture the text to ignore
var ignoreText = text.substring(tagPos, tagPos + tagLen);

// Catch up with the tag's position then output the tag
outputText(tagPos, 0, false);
output += '<i>' + htmlspecialchars_noquotes(ignoreText) + '</i>';
isRich = true;

// Move the cursor past this tag
pos = tagPos + tagLen;
}

/**
* Start a paragraph between current position and given position, if applicable
*
* @param  {number} maxPos Rightmost position at which the paragraph can be opened
*/
function outputParagraphStart(maxPos)
{
if (!HINT.RULE_CREATE_PARAGRAPHS)
{
return;
}

// Do nothing if we're already in a paragraph, or if we don't use paragraphs
if (context.inParagraph
|| !(context.flags & RULE_CREATE_PARAGRAPHS))
{
return;
}

// Output the whitespace between pos and maxPos if applicable
outputWhitespace(maxPos);

// Open the paragraph, but only if it's not at the very end of the text
if (pos < textLen)
{
output += '<p>';
context.inParagraph = true;
}
}

/**
* Close current paragraph at current position if applicable
*/
function outputParagraphEnd()
{
// Do nothing if we're not in a paragraph
if (!context.inParagraph)
{
return;
}

output += '</p>';
context.inParagraph = false;
}

/**
* Output the content of a verbatim tag
*
* @param {!Tag} tag
*/
function outputVerbatim(tag)
{
var flags = context.flags;
context.flags = tag.getFlags();
outputText(currentTag.getPos() + currentTag.getLen(), 0, false);
context.flags = flags;
}

/**
* Skip as much whitespace after current position as possible
*
* @param  {number} maxPos Rightmost character to be skipped
*/
function outputWhitespace(maxPos)
{
while (pos < maxPos && " \n\t".indexOf(text[pos]) > -1)
{
output += text[pos];
++pos;
}
}

//==========================================================================
// Plugins handling
//==========================================================================

/**
* Disable a plugin
*
* @param {string} pluginName Name of the plugin
*/
function disablePlugin(pluginName)
{
if (plugins[pluginName])
{
plugins[pluginName].isDisabled = true;
}
}

/**
* Enable a plugin
*
* @param {string} pluginName Name of the plugin
*/
function enablePlugin(pluginName)
{
if (plugins[pluginName])
{
plugins[pluginName].isDisabled = false;
}
}

/**
* Execute given plugin
*
* @param {string} pluginName Plugin's name
*/
function executePluginParser(pluginName)
{
var pluginConfig = plugins[pluginName];
if (pluginConfig.quickMatch && text.indexOf(pluginConfig.quickMatch) < 0)
{
return;
}

var matches = [];
if (HINT.regexp && HINT.regexpLimit && typeof pluginConfig.regexp !== 'undefined' && typeof pluginConfig.regexpLimit !== 'undefined')
{
matches = getMatches(pluginConfig.regexp, pluginConfig.regexpLimit);
if (!matches.length)
{
return;
}
}

// Execute the plugin's parser, which will add tags via addStartTag() and others
getPluginParser(pluginName)(text, matches);
}

/**
* Execute all the plugins
*/
function executePluginParsers()
{
for (var pluginName in plugins)
{
if (!plugins[pluginName].isDisabled)
{
executePluginParser(pluginName);
}
}
}

/**
* Get regexp matches in a manner similar to preg_match_all() with PREG_SET_ORDER | PREG_OFFSET_CAPTURE
*
* @param  {!RegExp} regexp
* @param  {number}  limit
* @return {!Array.<!Array>}
*/
function getMatches(regexp, limit)
{
// Reset the regexp
regexp.lastIndex = 0;
var matches = [], cnt = 0, m;
while (++cnt <= limit && (m = regexp.exec(text)))
{
// NOTE: coercing m.index to a number because Closure Compiler thinks pos is a string otherwise
var pos   = m.index,
match = [[m[0], pos]],
i = 0;
while (++i < m.length)
{
var str = m[i];

// Sub-expressions that were not evaluated return undefined
if (str === undefined)
{
match.push(['', -1]);
}
else
{
match.push([str, text.indexOf(str, pos)]);
pos += str.length;
}
}

matches.push(match);
}

return matches;
}

/**
* Get the callback for given plugin's parser
*
* @param  {string} pluginName
* @return {function(string, !Array)}
*/
function getPluginParser(pluginName)
{
return plugins[pluginName].parser;
}

/**
* Register a parser
*
* Can be used to add a new parser with no plugin config, or pre-generate a parser for an
* existing plugin
*
* @param  {string}    pluginName
* @param  {!Function} parser
* @param  {?RegExp=}  regexp
* @param  {number=}   limit
*/
function registerParser(pluginName, parser, regexp, limit)
{
// Create an empty config for this plugin to ensure it is executed
if (!plugins[pluginName])
{
plugins[pluginName] = {};
}
if (regexp)
{
plugins[pluginName].regexp = regexp;
plugins[pluginName].limit  = limit || Infinity;
}
plugins[pluginName].parser = parser;
}

//==========================================================================
// Rules handling
//==========================================================================

/**
* Apply closeAncestor rules associated with given tag
*
* @param  {!Tag}    tag Tag
* @return {boolean}     Whether a new tag has been added
*/
function closeAncestor(tag)
{
if (!HINT.closeAncestor)
{
return false;
}

if (openTags.length)
{
var tagName   = tag.getName(),
tagConfig = tagsConfig[tagName];

if (tagConfig.rules.closeAncestor)
{
var i = openTags.length;

while (--i >= 0)
{
var ancestor     = openTags[i],
ancestorName = ancestor.getName();

if (tagConfig.rules.closeAncestor[ancestorName])
{
++currentFixingCost;

// We have to close this ancestor. First we reinsert this tag...
tagStack.push(tag);

// ...then we add a new end tag for it with a better priority
addMagicEndTag(ancestor, tag.getPos(), tag.getSortPriority() - 1);

return true;
}
}
}
}

return false;
}

/**
* Apply closeParent rules associated with given tag
*
* @param  {!Tag}    tag Tag
* @return {boolean}     Whether a new tag has been added
*/
function closeParent(tag)
{
if (!HINT.closeParent)
{
return false;
}

if (openTags.length)
{
var tagName   = tag.getName(),
tagConfig = tagsConfig[tagName];

if (tagConfig.rules.closeParent)
{
var parent     = openTags[openTags.length - 1],
parentName = parent.getName();

if (tagConfig.rules.closeParent[parentName])
{
++currentFixingCost;

// We have to close that parent. First we reinsert the tag...
tagStack.push(tag);

// ...then we add a new end tag for it with a better priority
addMagicEndTag(parent, tag.getPos(), tag.getSortPriority() - 1);

return true;
}
}
}

return false;
}

/**
* Apply the createChild rules associated with given tag
*
* @param {!Tag} tag Tag
*/
function createChild(tag)
{
if (!HINT.createChild)
{
return;
}

var tagConfig = tagsConfig[tag.getName()];
if (tagConfig.rules.createChild)
{
var priority = -1000,
_text    = text.substring(pos),
tagPos   = pos + _text.length - _text.replace(/^[ \n\r\t]+/, '').length;
tagConfig.rules.createChild.forEach(function(tagName)
{
addStartTag(tagName, tagPos, 0, ++priority);
});
}
}

/**
* Apply fosterParent rules associated with given tag
*
* NOTE: this rule has the potential for creating an unbounded loop, either if a tag tries to
*       foster itself or two or more tags try to foster each other in a loop. We mitigate the
*       risk by preventing a tag from creating a child of itself (the parent still gets closed)
*       and by checking and increasing the currentFixingCost so that a loop of multiple tags
*       do not run indefinitely. The default tagLimit and nestingLimit also serve to prevent the
*       loop from running indefinitely
*
* @param  {!Tag}    tag Tag
* @return {boolean}     Whether a new tag has been added
*/
function fosterParent(tag)
{
if (!HINT.fosterParent)
{
return false;
}

if (openTags.length)
{
var tagName   = tag.getName(),
tagConfig = tagsConfig[tagName];

if (tagConfig.rules.fosterParent)
{
var parent     = openTags[openTags.length - 1],
parentName = parent.getName();

if (tagConfig.rules.fosterParent[parentName])
{
if (parentName !== tagName && currentFixingCost < maxFixingCost)
{
addFosterTag(tag, parent);
}

// Reinsert current tag
tagStack.push(tag);

// And finally close its parent with a priority that ensures it is processed
// before this tag
addMagicEndTag(parent, tag.getPos(), tag.getSortPriority() - 1);

// Adjust the fixing cost to account for the additional tags/processing
currentFixingCost += 4;

return true;
}
}
}

return false;
}

/**
* Apply requireAncestor rules associated with given tag
*
* @param  {!Tag}    tag Tag
* @return {boolean}     Whether this tag has an unfulfilled requireAncestor requirement
*/
function requireAncestor(tag)
{
if (!HINT.requireAncestor)
{
return false;
}

var tagName   = tag.getName(),
tagConfig = tagsConfig[tagName];

if (tagConfig.rules.requireAncestor)
{
var i = tagConfig.rules.requireAncestor.length;
while (--i >= 0)
{
var ancestorName = tagConfig.rules.requireAncestor[i];
if (cntOpen[ancestorName])
{
return false;
}
}

logger.err('Tag requires an ancestor', {
'requireAncestor' : tagConfig.rules.requireAncestor.join(', '),
'tag'             : tag
});

return true;
}

return false;
}

//==========================================================================
// Tag processing
//==========================================================================

/**
* Create and add a copy of a tag as a child of a given tag
*
* @param {!Tag} tag       Current tag
* @param {!Tag} fosterTag Tag to foster
*/
function addFosterTag(tag, fosterTag)
{
var coords    = getMagicStartCoords(tag.getPos() + tag.getLen()),
childPos  = coords[0],
childPrio = coords[1];

// Add a 0-width copy of the parent tag after this tag and make it depend on this tag
var childTag = addCopyTag(fosterTag, childPos, 0, childPrio);
tag.cascadeInvalidationTo(childTag);
}

/**
* Create and add an end tag for given start tag at given position
*
* @param  {!Tag}    startTag Start tag
* @param  {number}  tagPos   End tag's position (will be adjusted for whitespace if applicable)
* @param  {number=} prio     End tag's priority
* @return {!Tag}
*/
function addMagicEndTag(startTag, tagPos, prio)
{
var tagName = startTag.getName();

// Adjust the end tag's position if whitespace is to be minimized
if (HINT.RULE_IGNORE_WHITESPACE && ((currentTag.getFlags() | startTag.getFlags()) & RULE_IGNORE_WHITESPACE))
{
tagPos = getMagicEndPos(tagPos);
}

// Add a 0-width end tag that is paired with the given start tag
var endTag = addEndTag(tagName, tagPos, 0, prio || 0);
endTag.pairWith(startTag);

return endTag;
}

/**
* Compute the position of a magic end tag, adjusted for whitespace
*
* @param  {number} tagPos Rightmost possible position for the tag
* @return {number}
*/
function getMagicEndPos(tagPos)
{
// Back up from given position to the cursor's position until we find a character that
// is not whitespace
while (tagPos > pos && WHITESPACE.indexOf(text[tagPos - 1]) > -1)
{
--tagPos;
}

return tagPos;
}

/**
* Compute the position and priority of a magic start tag, adjusted for whitespace
*
* @param  {number} tagPos Leftmost possible position for the tag
* @return {!Array}        [Tag pos, priority]
*/
function getMagicStartCoords(tagPos)
{
var nextPos, nextPrio, nextTag, prio;
if (!tagStack.length)
{
// Set the next position outside the text boundaries
nextPos  = textLen + 1;
nextPrio = 0;
}
else
{
nextTag  = tagStack[tagStack.length - 1];
nextPos  = nextTag.getPos();
nextPrio = nextTag.getSortPriority();
}

// Find the first non-whitespace position before next tag or the end of text
while (tagPos < nextPos && WHITESPACE.indexOf(text[tagPos]) > -1)
{
++tagPos;
}

// Set a priority that ensures this tag appears before the next tag
prio = (tagPos === nextPos) ? nextPrio - 1 : 0;

return [tagPos, prio];
}

/**
* Test whether given start tag is immediately followed by a closing tag
*
* @param  {!Tag} tag Start tag (including self-closing)
* @return {boolean}
*/
function isFollowedByClosingTag(tag)
{
return (!tagStack.length) ? false : tagStack[tagStack.length - 1].canClose(tag);
}

/**
* Process all tags in the stack
*/
function processTags()
{
if (!tagStack.length)
{
return;
}

// Initialize the count tables
for (var tagName in tagsConfig)
{
cntOpen[tagName]  = 0;
cntTotal[tagName] = 0;
}

// Process the tag stack, close tags that were left open and repeat until done
do
{
while (tagStack.length)
{
if (!tagStackIsSorted)
{
sortTags();
}

currentTag = tagStack.pop();
processCurrentTag();
}

// Close tags that were left open
openTags.forEach(function (startTag)
{
// NOTE: we add tags in hierarchical order (ancestors to descendants) but since
//       the stack is processed in LIFO order, it means that tags get closed in
//       the correct order, from descendants to ancestors
addMagicEndTag(startTag, textLen);
});
}
while (tagStack.length);
}

/**
* Process current tag
*/
function processCurrentTag()
{
// Invalidate current tag if tags are disabled and current tag would not close the last open
// tag and is not a system tag
if ((context.flags & RULE_IGNORE_TAGS)
&& !currentTag.canClose(openTags[openTags.length - 1])
&& !currentTag.isSystemTag())
{
currentTag.invalidate();
}

var tagPos = currentTag.getPos(),
tagLen = currentTag.getLen();

// Test whether the cursor passed this tag's position already
if (pos > tagPos && !currentTag.isInvalid())
{
// Test whether this tag is paired with a start tag and this tag is still open
var startTag = currentTag.getStartTag();

if (startTag && openTags.indexOf(startTag) >= 0)
{
// Create an end tag that matches current tag's start tag, which consumes as much of
// the same text as current tag and is paired with the same start tag
addEndTag(
startTag.getName(),
pos,
Math.max(0, tagPos + tagLen - pos)
).pairWith(startTag);

// Note that current tag is not invalidated, it's merely replaced
return;
}

// If this is an ignore tag, try to ignore as much as the remaining text as possible
if (currentTag.isIgnoreTag())
{
var ignoreLen = tagPos + tagLen - pos;

if (ignoreLen > 0)
{
// Create a new ignore tag and move on
addIgnoreTag(pos, ignoreLen);

return;
}
}

// Skipped tags are invalidated
currentTag.invalidate();
}

if (currentTag.isInvalid())
{
return;
}

if (currentTag.isIgnoreTag())
{
outputIgnoreTag(currentTag);
}
else if (currentTag.isBrTag())
{
// Output the tag if it's allowed, ignore it otherwise
if (!HINT.RULE_PREVENT_BR || !(context.flags & RULE_PREVENT_BR))
{
outputBrTag(currentTag);
}
}
else if (currentTag.isParagraphBreak())
{
outputText(currentTag.getPos(), 0, true);
}
else if (currentTag.isVerbatim())
{
outputVerbatim(currentTag);
}
else if (currentTag.isStartTag())
{
processStartTag(currentTag);
}
else
{
processEndTag(currentTag);
}
}

/**
* Process given start tag (including self-closing tags) at current position
*
* @param {!Tag} tag Start tag (including self-closing)
*/
function processStartTag(tag)
{
var tagName   = tag.getName(),
tagConfig = tagsConfig[tagName];

// 1. Check that this tag has not reached its global limit tagLimit
// 2. Execute this tag's filterChain, which will filter/validate its attributes
// 3. Apply closeParent, closeAncestor and fosterParent rules
// 4. Check for nestingLimit
// 5. Apply requireAncestor rules
//
// This order ensures that the tag is valid and within the set limits before we attempt to
// close parents or ancestors. We need to close ancestors before we can check for nesting
// limits, whether this tag is allowed within current context (the context may change
// as ancestors are closed) or whether the required ancestors are still there (they might
// have been closed by a rule.)
if (cntTotal[tagName] >= tagConfig.tagLimit)
{
logger.err(
'Tag limit exceeded',
{
'tag'      : tag,
'tagName'  : tagName,
'tagLimit' : tagConfig.tagLimit
}
);
tag.invalidate();

return;
}

filterTag(tag);
if (tag.isInvalid())
{
return;
}

if (currentFixingCost < maxFixingCost)
{
if (fosterParent(tag) || closeParent(tag) || closeAncestor(tag))
{
// This tag parent/ancestor needs to be closed, we just return (the tag is still valid)
return;
}
}

if (cntOpen[tagName] >= tagConfig.nestingLimit)
{
logger.err(
'Nesting limit exceeded',
{
'tag'          : tag,
'tagName'      : tagName,
'nestingLimit' : tagConfig.nestingLimit
}
);
tag.invalidate();

return;
}

if (!tagIsAllowed(tagName))
{
var msg     = 'Tag is not allowed in this context',
context = {'tag': tag, 'tagName': tagName};
if (tag.getLen() > 0)
{
logger.warn(msg, context);
}
else
{
logger.debug(msg, context);
}
tag.invalidate();

return;
}

if (requireAncestor(tag))
{
tag.invalidate();

return;
}

// If this tag has an autoClose rule and it's not self-closed, paired with an end tag, or
// immediately followed by an end tag, we replace it with a self-closing tag with the same
// properties
if (HINT.RULE_AUTO_CLOSE
&& tag.getFlags() & RULE_AUTO_CLOSE
&& !tag.isSelfClosingTag()
&& !tag.getEndTag()
&& !isFollowedByClosingTag(tag))
{
var newTag = new Tag(Tag.SELF_CLOSING_TAG, tagName, tag.getPos(), tag.getLen());
newTag.setAttributes(tag.getAttributes());
newTag.setFlags(tag.getFlags());

tag = newTag;
}

if (HINT.RULE_TRIM_FIRST_LINE
&& tag.getFlags() & RULE_TRIM_FIRST_LINE
&& text[tag.getPos() + tag.getLen()] === "\n")
{
addIgnoreTag(tag.getPos() + tag.getLen(), 1);
}

// This tag is valid, output it and update the context
outputTag(tag);
pushContext(tag);

// Apply the createChild rules if applicable
createChild(tag);
}

/**
* Process given end tag at current position
*
* @param {!Tag} tag End tag
*/
function processEndTag(tag)
{
var tagName = tag.getName();

if (!cntOpen[tagName])
{
// This is an end tag with no start tag
return;
}

/**
* @type {!Array.<!Tag>} List of tags need to be closed before given tag
*/
var closeTags = [];

// Iterate through all open tags from last to first to find a match for our tag
var i = openTags.length;
while (--i >= 0)
{
var openTag = openTags[i];

if (tag.canClose(openTag))
{
break;
}

closeTags.push(openTag);
++currentFixingCost;
}

if (i < 0)
{
// Did not find a matching tag
logger.debug('Skipping end tag with no start tag', {'tag': tag});

return;
}

// Accumulate flags to determine whether whitespace should be trimmed
var flags = tag.getFlags();
closeTags.forEach(function(openTag)
{
flags |= openTag.getFlags();
});
var ignoreWhitespace = (HINT.RULE_IGNORE_WHITESPACE && (flags & RULE_IGNORE_WHITESPACE));

// Only reopen tags if we haven't exceeded our "fixing" budget
var keepReopening = HINT.RULE_AUTO_REOPEN && (currentFixingCost < maxFixingCost),
reopenTags    = [];
closeTags.forEach(function(openTag)
{
var openTagName = openTag.getName();

// Test whether this tag should be reopened automatically
if (keepReopening)
{
if (openTag.getFlags() & RULE_AUTO_REOPEN)
{
reopenTags.push(openTag);
}
else
{
keepReopening = false;
}
}

// Find the earliest position we can close this open tag
var tagPos = tag.getPos();
if (ignoreWhitespace)
{
tagPos = getMagicEndPos(tagPos);
}

// Output an end tag to close this start tag, then update the context
var endTag = new Tag(Tag.END_TAG, openTagName, tagPos, 0);
endTag.setFlags(openTag.getFlags());
outputTag(endTag);
popContext();
});

// Output our tag, moving the cursor past it, then update the context
outputTag(tag);
popContext();

// If our fixing budget allows it, peek at upcoming tags and remove end tags that would
// close tags that are already being closed now. Also, filter our list of tags being
// reopened by removing those that would immediately be closed
if (closeTags.length && currentFixingCost < maxFixingCost)
{
/**
* @type {number} Rightmost position of the portion of text to ignore
*/
var ignorePos = pos;

i = tagStack.length;
while (--i >= 0 && ++currentFixingCost < maxFixingCost)
{
var upcomingTag = tagStack[i];

// Test whether the upcoming tag is positioned at current "ignore" position and it's
// strictly an end tag (not a start tag or a self-closing tag)
if (upcomingTag.getPos() > ignorePos
|| upcomingTag.isStartTag())
{
break;
}

// Test whether this tag would close any of the tags we're about to reopen
var j = closeTags.length;

while (--j >= 0 && ++currentFixingCost < maxFixingCost)
{
if (upcomingTag.canClose(closeTags[j]))
{
// Remove the tag from the lists and reset the keys
closeTags.splice(j, 1);

if (reopenTags[j])
{
reopenTags.splice(j, 1);
}

// Extend the ignored text to cover this tag
ignorePos = Math.max(
ignorePos,
upcomingTag.getPos() + upcomingTag.getLen()
);

break;
}
}
}

if (ignorePos > pos)
{
/**
* @todo have a method that takes (pos,len) rather than a Tag
*/
outputIgnoreTag(new Tag(Tag.SELF_CLOSING_TAG, 'i', pos, ignorePos - pos));
}
}

// Re-add tags that need to be reopened, at current cursor position
reopenTags.forEach(function(startTag)
{
var newTag = addCopyTag(startTag, pos, 0);

// Re-pair the new tag
var endTag = startTag.getEndTag();
if (endTag)
{
newTag.pairWith(endTag);
}
});
}

/**
* Update counters and replace current context with its parent context
*/
function popContext()
{
var tag = openTags.pop();
--cntOpen[tag.getName()];
context = context.parentContext;
}

/**
* Update counters and replace current context with a new context based on given tag
*
* If given tag is a self-closing tag, the context won't change
*
* @param {!Tag} tag Start tag (including self-closing)
*/
function pushContext(tag)
{
var tagName   = tag.getName(),
tagFlags  = tag.getFlags(),
tagConfig = tagsConfig[tagName];

++cntTotal[tagName];

// If this is a self-closing tag, the context remains the same
if (tag.isSelfClosingTag())
{
return;
}

// Recompute the allowed tags
var allowed = [];
context.allowed.forEach(function(v, k)
{
// If the current tag is not transparent, override the low bits (allowed children) of
// current context with its high bits (allowed descendants)
if (!HINT.RULE_IS_TRANSPARENT || !(tagFlags & RULE_IS_TRANSPARENT))
{
v = (v & 0xFF00) | (v >> 8);
}
allowed.push(tagConfig.allowed[k] & v);
});

// Use this tag's flags as a base for this context and add inherited rules
var flags = tagFlags | (context.flags & RULES_INHERITANCE);

// RULE_DISABLE_AUTO_BR turns off RULE_ENABLE_AUTO_BR
if (flags & RULE_DISABLE_AUTO_BR)
{
flags &= ~RULE_ENABLE_AUTO_BR;
}

++cntOpen[tagName];
openTags.push(tag);
context         = { parentContext : context };
context.allowed = allowed;
context.flags   = flags;
}

/**
* Return whether given tag is allowed in current context
*
* @param  {string}  tagName
* @return {boolean}
*/
function tagIsAllowed(tagName)
{
var n = tagsConfig[tagName].bitNumber;

return !!(context.allowed[n >> 3] & (1 << (n & 7)));
}

//==========================================================================
// Tag stack
//==========================================================================

/**
* Add a start tag
*
* @param  {string}  name Name of the tag
* @param  {number}  pos  Position of the tag in the text
* @param  {number}  len  Length of text consumed by the tag
* @param  {number=} prio Tags' priority
* @return {!Tag}
*/
function addStartTag(name, pos, len, prio)
{
return addTag(Tag.START_TAG, name, pos, len, prio || 0);
}

/**
* Add an end tag
*
* @param  {string}  name Name of the tag
* @param  {number}  pos  Position of the tag in the text
* @param  {number}  len  Length of text consumed by the tag
* @param  {number=} prio Tags' priority
* @return {!Tag}
*/
function addEndTag(name, pos, len, prio)
{
return addTag(Tag.END_TAG, name, pos, len, prio || 0);
}

/**
* Add a self-closing tag
*
* @param  {string}  name Name of the tag
* @param  {number}  pos  Position of the tag in the text
* @param  {number}  len  Length of text consumed by the tag
* @param  {number=} prio Tags' priority
* @return {!Tag}
*/
function addSelfClosingTag(name, pos, len, prio)
{
return addTag(Tag.SELF_CLOSING_TAG, name, pos, len, prio || 0);
}

/**
* Add a 0-width "br" tag to force a line break at given position
*
* @param  {number}  pos  Position of the tag in the text
* @param  {number=} prio Tags' priority
* @return {!Tag}
*/
function addBrTag(pos, prio)
{
return addTag(Tag.SELF_CLOSING_TAG, 'br', pos, 0, prio || 0);
}

/**
* Add an "ignore" tag
*
* @param  {number}  pos  Position of the tag in the text
* @param  {number}  len  Length of text consumed by the tag
* @param  {number=} prio Tags' priority
* @return {!Tag}
*/
function addIgnoreTag(pos, len, prio)
{
return addTag(Tag.SELF_CLOSING_TAG, 'i', pos, Math.min(len, textLen - pos), prio || 0);
}

/**
* Add a paragraph break at given position
*
* Uses a zero-width tag that is actually never output in the result
*
* @param  {number}  pos  Position of the tag in the text
* @param  {number=} prio Tags' priority
* @return {!Tag}
*/
function addParagraphBreak(pos, prio)
{
return addTag(Tag.SELF_CLOSING_TAG, 'pb', pos, 0, prio || 0);
}

/**
* Add a copy of given tag at given position and length
*
* @param  {!Tag}    tag  Original tag
* @param  {number}  pos  Copy's position
* @param  {number}  len  Copy's length
* @param  {number=} prio Tags' priority
* @return {!Tag}         Copy tag
*/
function addCopyTag(tag, pos, len, prio)
{
var copy = addTag(tag.getType(), tag.getName(), pos, len, tag.getSortPriority());
copy.setAttributes(tag.getAttributes());

return copy;
}

/**
* Add a tag
*
* @param  {number}  type Tag's type
* @param  {string}  name Name of the tag
* @param  {number}  pos  Position of the tag in the text
* @param  {number}  len  Length of text consumed by the tag
* @param  {number=} prio Tags' priority
* @return {!Tag}
*/
function addTag(type, name, pos, len, prio)
{
// Create the tag
var tag = new Tag(type, name, pos, len, prio || 0);

// Set this tag's rules bitfield
if (tagsConfig[name])
{
tag.setFlags(tagsConfig[name].rules.flags);
}

// Invalidate this tag if it's an unknown tag, a disabled tag, if either of its length or
// position is negative or if it's out of bounds
if ((!tagsConfig[name] && !tag.isSystemTag()) || isInvalidTextSpan(pos, len))
{
tag.invalidate();
}
else if (tagsConfig[name] && tagsConfig[name].isDisabled)
{
logger.warn(
'Tag is disabled',
{
'tag'     : tag,
'tagName' : name
}
);
tag.invalidate();
}
else
{
insertTag(tag);
}

return tag;
}

/**
* Test whether given text span is outside text boundaries or an invalid UTF sequence
*
* @param  {number}  pos Start of text
* @param  {number}  len Length of text
* @return {boolean}
*/
function isInvalidTextSpan(pos, len)
{
return (len < 0 || pos < 0 || pos + len > textLen || /[\uDC00-\uDFFF]/.test(text.substring(pos, pos + 1) + text.substring(pos + len, pos + len + 1)));
}

/**
* Insert given tag in the tag stack
*
* @param {!Tag} tag
*/
function insertTag(tag)
{
if (!tagStackIsSorted)
{
tagStack.push(tag);
}
else
{
// Scan the stack and copy every tag to the next slot until we find the correct index
var i   = tagStack.length,
key = getSortKey(tag);
while (i > 0 && key > getSortKey(tagStack[i - 1]))
{
tagStack[i] = tagStack[i - 1];
--i;
}
tagStack[i] = tag;
}
}

/**
* Add a pair of tags
*
* @param  {string} name     Name of the tags
* @param  {number} startPos Position of the start tag
* @param  {number} startLen Length of the start tag
* @param  {number} endPos   Position of the start tag
* @param  {number} endLen   Length of the start tag
* @param  {number=}  prio     Start tag's priority (the end tag will be set to minus that value)
* @return {!Tag}             Start tag
*/
function addTagPair(name, startPos, startLen, endPos, endLen, prio)
{
// NOTE: the end tag is added first to try to keep the stack in the correct order
var endTag   = addEndTag(name, endPos, endLen, -prio || 0),
startTag = addStartTag(name, startPos, startLen, prio || 0);
startTag.pairWith(endTag);

return startTag;
}

/**
* Add a tag that represents a verbatim copy of the original text
*
* @param  {number} pos  Position of the tag in the text
* @param  {number} len  Length of text consumed by the tag
* @param  {number=} prio Tag's priority
* @return {!Tag}
*/
function addVerbatim(pos, len, prio)
{
return addTag(Tag.SELF_CLOSING_TAG, 'v', pos, len, prio || 0);
}

/**
* Sort tags by position and precedence
*/
function sortTags()
{
var arr  = {},
keys = [],
i    = tagStack.length;
while (--i >= 0)
{
var tag = tagStack[i],
key = getSortKey(tag, i);
keys.push(key);
arr[key] = tag;
}
keys.sort();

i = keys.length;
tagStack = [];
while (--i >= 0)
{
tagStack.push(arr[keys[i]]);
}

tagStackIsSorted = true;
}

/**
* Generate a key for given tag that can be used to compare its position using lexical comparisons
*
* Tags are sorted by position first, then by priority, then by whether they consume any text,
* then by length, and finally in order of their creation.
*
* The stack's array is in reverse order. Therefore, tags that appear at the start of the text
* are at the end of the array.
*
* @param  {!Tag}    tag
* @param  {number=} tagIndex
* @return {string}
*/
function getSortKey(tag, tagIndex)
{
// Ensure that negative values are sorted correctly by flagging them and making them positive
var prioFlag = (tag.getSortPriority() >= 0),
prio     = tag.getSortPriority();
if (!prioFlag)
{
prio += (1 << 30);
}

// Sort 0-width tags separately from the rest
var lenFlag = (tag.getLen() > 0),
lenOrder;
if (lenFlag)
{
// Inverse their length so that longest matches are processed first
lenOrder = textLen - tag.getLen();
}
else
{
// Sort self-closing tags in-between start tags and end tags to keep them outside of tag
// pairs
var order = {};
order[Tag.END_TAG]          = 0;
order[Tag.SELF_CLOSING_TAG] = 1;
order[Tag.START_TAG]        = 2;
lenOrder = order[tag.getType()];
}

return hex32(tag.getPos()) + (+prioFlag) + hex32(prio) + (+lenFlag) + hex32(lenOrder) + hex32(tagIndex || 0);
}

/**
* Format given number to a 32 bit hex value
*
* @param  {number} number
* @return {string}
*/
function hex32(number)
{
var hex = number.toString(16);

return "        ".substring(hex.length) + hex;
}