src/Parser.php

<?php

/**
* @package   s9e\TextFormatter
* @copyright Copyright (c) The s9e authors
* @license   http://www.opensource.org/licenses/mit-license.php The MIT License
*/
namespace s9e\TextFormatter;

use InvalidArgumentException;
use RuntimeException;
use s9e\TextFormatter\Parser\FilterProcessing;
use s9e\TextFormatter\Parser\Logger;
use s9e\TextFormatter\Parser\Tag;

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

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

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

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

	/**
	* @var array Number of open tags for each tag name
	*/
	protected $cntOpen;

	/**
	* @var array Number of times each tag has been used
	*/
	protected $cntTotal;

	/**
	* @var array Current context
	*/
	protected $context;

	/**
	* @var integer How hard the parser has worked on fixing bad markup so far
	*/
	protected $currentFixingCost;

	/**
	* @var Tag Current tag being processed
	*/
	protected $currentTag;

	/**
	* @var bool Whether the output contains "rich" tags, IOW any tag that is not <p> or <br/>
	*/
	protected $isRich;

	/**
	* @var Logger This parser's logger
	*/
	protected $logger;

	/**
	* @var integer How hard the parser should work on fixing bad markup
	*/
	public $maxFixingCost = 10000;

	/**
	* @var array Associative array of namespace prefixes in use in document (prefixes used as key)
	*/
	protected $namespaces;

	/**
	* @var array Stack of open tags (instances of Tag)
	*/
	protected $openTags;

	/**
	* @var string This parser's output
	*/
	protected $output;

	/**
	* @var integer Position of the cursor in the original text
	*/
	protected $pos;

	/**
	* @var array Array of callbacks, using plugin names as keys
	*/
	protected $pluginParsers = [];

	/**
	* @var array Associative array of [pluginName => pluginConfig]
	*/
	protected $pluginsConfig;

	/**
	* @var array Variables registered for use in filters
	*/
	public $registeredVars = [];

	/**
	* @var array Root context, used at the root of the document
	*/
	protected $rootContext;

	/**
	* @var array Tags' config
	*/
	protected $tagsConfig;

	/**
	* @var array Tag storage
	*/
	protected $tagStack;

	/**
	* @var bool Whether the tags in the stack are sorted
	*/
	protected $tagStackIsSorted;

	/**
	* @var string Text being parsed
	*/
	protected $text;

	/**
	* @var integer Length of the text being parsed
	*/
	protected $textLen;

	/**
	* @var integer Counter incremented everytime the parser is reset. Used to as a canary to detect
	*              whether the parser was reset during execution
	*/
	protected $uid = 0;

	/**
	* @var integer Position before which we output text verbatim, without paragraphs or linebreaks
	*/
	protected $wsPos;

	/**
	* Constructor
	*/
	public function __construct(array $config)
	{
		$this->pluginsConfig  = $config['plugins'];
		$this->registeredVars = $config['registeredVars'];
		$this->rootContext    = $config['rootContext'];
		$this->tagsConfig     = $config['tags'];

		$this->__wakeup();
	}

	/**
	* Serializer
	*
	* Returns the properties that need to persist through serialization.
	*
	* NOTE: using __sleep() is preferable to implementing Serializable because it leaves the choice
	* of the serializer to the user (e.g. igbinary)
	*
	* @return array
	*/
	public function __sleep()
	{
		return ['pluginsConfig', 'registeredVars', 'rootContext', 'tagsConfig'];
	}

	/**
	* Unserializer
	*
	* @return void
	*/
	public function __wakeup()
	{
		$this->logger = new Logger;
	}

	/**
	* Reset the parser for a new parsing
	*
	* @param  string $text Text to be parsed
	* @return void
	*/
	protected function reset($text)
	{
		// Reject invalid UTF-8
		if (!preg_match('//u', $text))
		{
			throw new InvalidArgumentException('Invalid UTF-8 input');
		}

		// Normalize CR/CRLF to LF, remove characters that aren't allowed in XML
		$text = preg_replace('/\\r\\n?/', "\n", $text);
		$text = preg_replace('/[\\x00-\\x08\\x0B\\x0C\\x0E-\\x1F]|\\xEF\\xBF[\\xBE\\xBF]/', '', $text);

		// Clear the logs
		$this->logger->clear();

		// Initialize the rest
		$this->cntOpen           = [];
		$this->cntTotal          = [];
		$this->currentFixingCost = 0;
		$this->currentTag        = null;
		$this->isRich            = false;
		$this->namespaces        = [];
		$this->openTags          = [];
		$this->output            = '';
		$this->pos               = 0;
		$this->tagStack          = [];
		$this->tagStackIsSorted  = false;
		$this->text              = $text;
		$this->textLen           = strlen($text);
		$this->wsPos             = 0;

		// Initialize the root context
		$this->context = $this->rootContext;
		$this->context['inParagraph'] = false;

		// Bump the UID
		++$this->uid;
	}

	/**
	* Set a tag's option
	*
	* This method ensures that the tag's config is a value and not a reference, to prevent
	* potential side-effects. References contained *inside* the tag's config are left untouched
	*
	* @param  string $tagName     Tag's name
	* @param  string $optionName  Option's name
	* @param  mixed  $optionValue Option's value
	* @return void
	*/
	protected function setTagOption($tagName, $optionName, $optionValue)
	{
		if (isset($this->tagsConfig[$tagName]))
		{
			// Copy the tag's config and remove it. That will destroy the reference
			$tagConfig = $this->tagsConfig[$tagName];
			unset($this->tagsConfig[$tagName]);

			// Set the new value and replace the tag's config
			$tagConfig[$optionName]     = $optionValue;
			$this->tagsConfig[$tagName] = $tagConfig;
		}
	}

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

	/**
	* Disable a tag
	*
	* @param  string $tagName Name of the tag
	* @return void
	*/
	public function disableTag($tagName)
	{
		$this->setTagOption($tagName, 'isDisabled', true);
	}

	/**
	* Enable a tag
	*
	* @param  string $tagName Name of the tag
	* @return void
	*/
	public function enableTag($tagName)
	{
		if (isset($this->tagsConfig[$tagName]))
		{
			unset($this->tagsConfig[$tagName]['isDisabled']);
		}
	}

	/**
	* Get this parser's Logger instance
	*
	* @return Logger
	*/
	public function getLogger()
	{
		return $this->logger;
	}

	/**
	* Return the last text parsed
	*
	* This method returns the normalized text, which may be slightly different from the original
	* text in that EOLs are normalized to LF and other control codes are stripped. This method is
	* meant to be used in support of processing log entries, which contain offsets based on the
	* normalized text
	*
	* @see Parser::reset()
	*
	* @return string
	*/
	public function getText()
	{
		return $this->text;
	}

	/**
	* Parse a text
	*
	* @param  string $text Text to parse
	* @return string       XML representation
	*/
	public function parse($text)
	{
		// Reset the parser and save the uid
		$this->reset($text);
		$uid = $this->uid;

		// Do the heavy lifting
		$this->executePluginParsers();
		$this->processTags();

		// Finalize the document
		$this->finalizeOutput();

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

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

		return $this->output;
	}

	/**
	* 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  integer $tagLimit
	* @return void
	*/
	public function setTagLimit($tagName, $tagLimit)
	{
		$this->setTagOption($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  integer $nestingLimit
	* @return void
	*/
	public function setNestingLimit($tagName, $nestingLimit)
	{
		$this->setTagOption($tagName, 'nestingLimit', $nestingLimit);
	}

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

	/**
	* Finalize the output by appending the rest of the unprocessed text and create the root node
	*
	* @return void
	*/
	protected function finalizeOutput()
	{
		// Output the rest of the text and close the last paragraph
		$this->outputText($this->textLen, 0, true);

		// Remove empty tag pairs, e.g. <I><U></U></I> as well as empty paragraphs
		do
		{
			$this->output = preg_replace('(<([^ />]++)[^>]*></\\1>)', '', $this->output, -1, $cnt);
		}
		while ($cnt > 0);

		// Merge consecutive <i> tags
		if (strpos($this->output, '</i><i>') !== false)
		{
			$this->output = str_replace('</i><i>', '', $this->output);
		}

		// Remove illegal characters from the output to ensure it's valid XML
		$this->output = preg_replace('([\\x00-\\x08\\x0B-\\x1F]|\\xEF\\xBF[\\xBE\\xBF])', '', $this->output);

		// Encode Unicode characters that are outside of the BMP
		$this->output = Utils::encodeUnicodeSupplementaryCharacters($this->output);

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

		// Prepare the root node with all the namespace declarations
		$tmp = '<' . $tagName;
		foreach (array_keys($this->namespaces) as $prefix)
		{
			$tmp .= ' xmlns:' . $prefix . '="urn:s9e:TextFormatter:' . $prefix . '"';
		}

		$this->output = $tmp . '>' . $this->output . '</' . $tagName . '>';
	}

	/**
	* Append a tag to the output
	*
	* @param  Tag  $tag Tag to append
	* @return void
	*/
	protected function outputTag(Tag $tag)
	{
		$this->isRich = true;

		$tagName  = $tag->getName();
		$tagPos   = $tag->getPos();
		$tagLen   = $tag->getLen();
		$tagFlags = $tag->getFlags();

		if ($tagFlags & self::RULE_IGNORE_WHITESPACE)
		{
			$skipBefore = 1;
			$skipAfter  = ($tag->isEndTag()) ? 2 : 1;
		}
		else
		{
			$skipBefore = $skipAfter = 0;
		}

		// 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)
		$closeParagraph = (!$tag->isStartTag() || ($tagFlags & self::RULE_BREAK_PARAGRAPH));

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

		// Capture the text consumed by the tag
		$tagText = ($tagLen)
		         ? htmlspecialchars(substr($this->text, $tagPos, $tagLen), ENT_NOQUOTES, 'UTF-8')
		         : '';

		// Output current tag
		if ($tag->isStartTag())
		{
			// Handle paragraphs before opening the tag
			if (!($tagFlags & self::RULE_BREAK_PARAGRAPH))
			{
				$this->outputParagraphStart($tagPos);
			}

			// Record this tag's namespace, if applicable
			$colonPos = strpos($tagName, ':');
			if ($colonPos)
			{
				$this->namespaces[substr($tagName, 0, $colonPos)] = 0;
			}

			// Open the start tag and add its attributes, but don't close the tag
			$this->output .= '<' . $tagName;

			// We output the attributes in lexical order. Helps canonicalizing the output and could
			// prove useful someday
			$attributes = $tag->getAttributes();
			ksort($attributes);

			foreach ($attributes as $attrName => $attrValue)
			{
				$this->output .= ' ' . $attrName . '="' . str_replace("\n", '&#10;', htmlspecialchars($attrValue, ENT_COMPAT, 'UTF-8')) . '"';
			}

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

			$this->output .= '</' . $tagName . '>';
		}

		// Move the cursor past the tag
		$this->pos = $tagPos + $tagLen;

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

			// Move the cursor past the newline
			++$this->wsPos;
		}
	}

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

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

			return;
		}

		// Skip over previously identified whitespace if applicable
		if ($this->wsPos > $this->pos)
		{
			$skipPos       = min($catchupPos, $this->wsPos);
			$this->output .= substr($this->text, $this->pos, $skipPos - $this->pos);
			$this->pos     = $skipPos;

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

				return;
			}
		}

		// Test whether we're even supposed to output anything
		if ($this->context['flags'] & self::RULE_IGNORE_TEXT)
		{
			$catchupLen  = $catchupPos - $this->pos;
			$catchupText = substr($this->text, $this->pos, $catchupLen);

			// If the catchup text is not entirely composed of whitespace, we put it inside ignore
			// tags
			if (strspn($catchupText, " \n\t") < $catchupLen)
			{
				$catchupText = '<i>' . htmlspecialchars($catchupText, ENT_NOQUOTES, 'UTF-8') . '</i>';
			}

			$this->output .= $catchupText;
			$this->pos = $catchupPos;

			if ($closeParagraph)
			{
				$this->outputParagraphEnd();
			}

			return;
		}

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

		// Ignore as many lines (including whitespace) as specified
		while ($maxLines && --$ignorePos >= $this->pos)
		{
			$c = $this->text[$ignorePos];
			if (strpos(self::WHITESPACE, $c) === false)
			{
				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 ($this->context['flags'] & self::RULE_CREATE_PARAGRAPHS)
		{
			if (!$this->context['inParagraph'])
			{
				$this->outputWhitespace($catchupPos);

				if ($catchupPos > $this->pos)
				{
					$this->outputParagraphStart($catchupPos);
				}
			}

			// Look for a paragraph break in this text
			$pbPos = strpos($this->text, "\n\n", $this->pos);

			while ($pbPos !== false && $pbPos < $catchupPos)
			{
				$this->outputText($pbPos, 0, true);
				$this->outputParagraphStart($catchupPos);

				$pbPos = strpos($this->text, "\n\n", $this->pos);
			}
		}

		// Capture, escape and output the text
		if ($catchupPos > $this->pos)
		{
			$catchupText = htmlspecialchars(
				substr($this->text, $this->pos, $catchupPos - $this->pos),
				ENT_NOQUOTES,
				'UTF-8'
			);

			// Format line breaks if applicable
			if (($this->context['flags'] & self::RULES_AUTO_LINEBREAKS) === self::RULE_ENABLE_AUTO_BR)
			{
				$catchupText = str_replace("\n", "<br/>\n", $catchupText);
			}

			$this->output .= $catchupText;
		}

		// Close the paragraph if applicable
		if ($closeParagraph)
		{
			$this->outputParagraphEnd();
		}

		// Add the ignored text if applicable
		if ($ignoreLen)
		{
			$this->output .= substr($this->text, $catchupPos, $ignoreLen);
		}

		// Move the cursor past the text
		$this->pos = $catchupPos + $ignoreLen;
	}

	/**
	* Output a linebreak tag
	*
	* @param  Tag  $tag
	* @return void
	*/
	protected function outputBrTag(Tag $tag)
	{
		$this->outputText($tag->getPos(), 0, false);
		$this->output .= '<br/>';
	}

	/**
	* Output an ignore tag
	*
	* @param  Tag  $tag
	* @return void
	*/
	protected function outputIgnoreTag(Tag $tag)
	{
		$tagPos = $tag->getPos();
		$tagLen = $tag->getLen();

		// Capture the text to ignore
		$ignoreText = substr($this->text, $tagPos, $tagLen);

		// Catch up with the tag's position then output the tag
		$this->outputText($tagPos, 0, false);
		$this->output .= '<i>' . htmlspecialchars($ignoreText, ENT_NOQUOTES, 'UTF-8') . '</i>';
		$this->isRich = true;

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

	/**
	* Start a paragraph between current position and given position, if applicable
	*
	* @param  integer $maxPos Rightmost position at which the paragraph can be opened
	* @return void
	*/
	protected function outputParagraphStart($maxPos)
	{
		// Do nothing if we're already in a paragraph, or if we don't use paragraphs
		if ($this->context['inParagraph']
		 || !($this->context['flags'] & self::RULE_CREATE_PARAGRAPHS))
		{
			return;
		}

		// Output the whitespace between $this->pos and $maxPos if applicable
		$this->outputWhitespace($maxPos);

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

	/**
	* Close current paragraph at current position if applicable
	*
	* @return void
	*/
	protected function outputParagraphEnd()
	{
		// Do nothing if we're not in a paragraph
		if (!$this->context['inParagraph'])
		{
			return;
		}

		$this->output .= '</p>';
		$this->context['inParagraph'] = false;
	}

	/**
	* Output the content of a verbatim tag
	*
	* @param  Tag  $tag
	* @return void
	*/
	protected function outputVerbatim(Tag $tag)
	{
		$flags = $this->context['flags'];
		$this->context['flags'] = $tag->getFlags();
		$this->outputText($this->currentTag->getPos() + $this->currentTag->getLen(), 0, false);
		$this->context['flags'] = $flags;
	}

	/**
	* Skip as much whitespace after current position as possible
	*
	* @param  integer $maxPos Rightmost character to be skipped
	* @return void
	*/
	protected function outputWhitespace($maxPos)
	{
		if ($maxPos > $this->pos)
		{
			$spn = strspn($this->text, self::WHITESPACE, $this->pos, $maxPos - $this->pos);

			if ($spn)
			{
				$this->output .= substr($this->text, $this->pos, $spn);
				$this->pos += $spn;
			}
		}
	}

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

	/**
	* Disable a plugin
	*
	* @param  string $pluginName Name of the plugin
	* @return void
	*/
	public function disablePlugin($pluginName)
	{
		if (isset($this->pluginsConfig[$pluginName]))
		{
			// Copy the plugin's config to remove the reference
			$pluginConfig = $this->pluginsConfig[$pluginName];
			unset($this->pluginsConfig[$pluginName]);

			// Update the value and replace the plugin's config
			$pluginConfig['isDisabled'] = true;
			$this->pluginsConfig[$pluginName] = $pluginConfig;
		}
	}

	/**
	* Enable a plugin
	*
	* @param  string $pluginName Name of the plugin
	* @return void
	*/
	public function enablePlugin($pluginName)
	{
		if (isset($this->pluginsConfig[$pluginName]))
		{
			$this->pluginsConfig[$pluginName]['isDisabled'] = false;
		}
	}

	/**
	* Execute given plugin
	*
	* @param  string $pluginName Plugin's name
	* @return void
	*/
	protected function executePluginParser($pluginName)
	{
		$pluginConfig = $this->pluginsConfig[$pluginName];
		if (isset($pluginConfig['quickMatch']) && strpos($this->text, $pluginConfig['quickMatch']) === false)
		{
			return;
		}

		$matches = [];
		if (isset($pluginConfig['regexp'], $pluginConfig['regexpLimit']))
		{
			$matches = $this->getMatches($pluginConfig['regexp'], $pluginConfig['regexpLimit']);
			if (empty($matches))
			{
				return;
			}
		}

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

	/**
	* Execute all the plugins
	*
	* @return void
	*/
	protected function executePluginParsers()
	{
		foreach ($this->pluginsConfig as $pluginName => $pluginConfig)
		{
			if (empty($pluginConfig['isDisabled']))
			{
				$this->executePluginParser($pluginName);
			}
		}
	}

	/**
	* Execute given regexp and returns as many matches as given limit
	*
	* @param  string  $regexp
	* @param  integer $limit
	* @return array
	*/
	protected function getMatches($regexp, $limit)
	{
		$cnt = preg_match_all($regexp, $this->text, $matches, PREG_SET_ORDER | PREG_OFFSET_CAPTURE);
		if ($cnt > $limit)
		{
			$matches = array_slice($matches, 0, $limit);
		}

		return $matches;
	}

	/**
	* Get the cached callback for given plugin's parser
	*
	* @param  string $pluginName Plugin's name
	* @return callable
	*/
	protected function getPluginParser($pluginName)
	{
		// Cache a new instance of this plugin's parser if there isn't one already
		if (!isset($this->pluginParsers[$pluginName]))
		{
			$pluginConfig = $this->pluginsConfig[$pluginName];
			$className = (isset($pluginConfig['className']))
			           ? $pluginConfig['className']
			           : 's9e\\TextFormatter\\Plugins\\' . $pluginName . '\\Parser';

			// Register the parser as a callback
			$this->pluginParsers[$pluginName] = [new $className($this, $pluginConfig), 'parse'];
		}

		return $this->pluginParsers[$pluginName];
	}

	/**
	* 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  callable $parser
	* @param  string   $regexp
	* @param  integer  $limit
	* @return void
	*/
	public function registerParser($pluginName, $parser, $regexp = null, $limit = PHP_INT_MAX)
	{
		if (!is_callable($parser))
		{
			throw new InvalidArgumentException('Argument 1 passed to ' . __METHOD__ . ' must be a valid callback');
		}
		// Create an empty config for this plugin to ensure it is executed
		if (!isset($this->pluginsConfig[$pluginName]))
		{
			$this->pluginsConfig[$pluginName] = [];
		}
		if (isset($regexp))
		{
			$this->pluginsConfig[$pluginName]['regexp']      = $regexp;
			$this->pluginsConfig[$pluginName]['regexpLimit'] = $limit;
		}
		$this->pluginParsers[$pluginName] = $parser;
	}

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

	/**
	* Apply closeAncestor rules associated with given tag
	*
	* @param  Tag  $tag Tag
	* @return bool      Whether a new tag has been added
	*/
	protected function closeAncestor(Tag $tag)
	{
		if (!empty($this->openTags))
		{
			$tagName   = $tag->getName();
			$tagConfig = $this->tagsConfig[$tagName];

			if (!empty($tagConfig['rules']['closeAncestor']))
			{
				$i = count($this->openTags);

				while (--$i >= 0)
				{
					$ancestor     = $this->openTags[$i];
					$ancestorName = $ancestor->getName();

					if (isset($tagConfig['rules']['closeAncestor'][$ancestorName]))
					{
						++$this->currentFixingCost;

						// We have to close this ancestor. First we reinsert this tag...
						$this->tagStack[] = $tag;

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

						return true;
					}
				}
			}
		}

		return false;
	}

	/**
	* Apply closeParent rules associated with given tag
	*
	* @param  Tag  $tag Tag
	* @return bool      Whether a new tag has been added
	*/
	protected function closeParent(Tag $tag)
	{
		if (!empty($this->openTags))
		{
			$tagName   = $tag->getName();
			$tagConfig = $this->tagsConfig[$tagName];

			if (!empty($tagConfig['rules']['closeParent']))
			{
				$parent     = end($this->openTags);
				$parentName = $parent->getName();

				if (isset($tagConfig['rules']['closeParent'][$parentName]))
				{
					++$this->currentFixingCost;

					// We have to close that parent. First we reinsert the tag...
					$this->tagStack[] = $tag;

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

					return true;
				}
			}
		}

		return false;
	}

	/**
	* Apply the createChild rules associated with given tag
	*
	* @param  Tag  $tag Tag
	* @return void
	*/
	protected function createChild(Tag $tag)
	{
		$tagConfig = $this->tagsConfig[$tag->getName()];
		if (isset($tagConfig['rules']['createChild']))
		{
			$priority = -1000;
			$tagPos   = $this->pos + strspn($this->text, " \n\r\t", $this->pos);
			foreach ($tagConfig['rules']['createChild'] as $tagName)
			{
				$this->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 bool      Whether a new tag has been added
	*/
	protected function fosterParent(Tag $tag)
	{
		if (!empty($this->openTags))
		{
			$tagName   = $tag->getName();
			$tagConfig = $this->tagsConfig[$tagName];

			if (!empty($tagConfig['rules']['fosterParent']))
			{
				$parent     = end($this->openTags);
				$parentName = $parent->getName();

				if (isset($tagConfig['rules']['fosterParent'][$parentName]))
				{
					if ($parentName !== $tagName && $this->currentFixingCost < $this->maxFixingCost)
					{
						$this->addFosterTag($tag, $parent);
					}

					// Reinsert current tag
					$this->tagStack[] = $tag;

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

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

					return true;
				}
			}
		}

		return false;
	}

	/**
	* Apply requireAncestor rules associated with given tag
	*
	* @param  Tag  $tag Tag
	* @return bool      Whether this tag has an unfulfilled requireAncestor requirement
	*/
	protected function requireAncestor(Tag $tag)
	{
		$tagName   = $tag->getName();
		$tagConfig = $this->tagsConfig[$tagName];

		if (isset($tagConfig['rules']['requireAncestor']))
		{
			foreach ($tagConfig['rules']['requireAncestor'] as $ancestorName)
			{
				if (!empty($this->cntOpen[$ancestorName]))
				{
					return false;
				}
			}

			$this->logger->err('Tag requires an ancestor', [
				'requireAncestor' => implode(',', $tagConfig['rules']['requireAncestor']),
				'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
	* @return void
	*/
	protected function addFosterTag(Tag $tag, Tag $fosterTag)
	{
		list($childPos, $childPrio) = $this->getMagicStartCoords($tag->getPos() + $tag->getLen());

		// Add a 0-width copy of the parent tag after this tag and make it depend on this tag
		$childTag = $this->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  integer $tagPos   End tag's position (will be adjusted for whitespace if applicable)
	* @param  integer $prio     End tag's priority
	* @return Tag
	*/
	protected function addMagicEndTag(Tag $startTag, $tagPos, $prio = 0)
	{
		$tagName = $startTag->getName();

		// Adjust the end tag's position if whitespace is to be minimized
		if (($this->currentTag->getFlags() | $startTag->getFlags()) & self::RULE_IGNORE_WHITESPACE)
		{
			$tagPos = $this->getMagicEndPos($tagPos);
		}

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

		return $endTag;
	}

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

		return $tagPos;
	}

	/**
	* Compute the position and priority of a magic start tag, adjusted for whitespace
	*
	* @param  integer   $tagPos Leftmost possible position for the tag
	* @return integer[]         [Tag pos, priority]
	*/
	protected function getMagicStartCoords($tagPos)
	{
		if (empty($this->tagStack))
		{
			// Set the next position outside the text boundaries
			$nextPos  = $this->textLen + 1;
			$nextPrio = 0;
		}
		else
		{
			$nextTag  = end($this->tagStack);
			$nextPos  = $nextTag->getPos();
			$nextPrio = $nextTag->getSortPriority();
		}

		// Find the first non-whitespace position before next tag or the end of text
		while ($tagPos < $nextPos && strpos(self::WHITESPACE, $this->text[$tagPos]) !== false)
		{
			++$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
	* @return bool
	*/
	protected function isFollowedByClosingTag(Tag $tag)
	{
		return (empty($this->tagStack)) ? false : end($this->tagStack)->canClose($tag);
	}

	/**
	* Process all tags in the stack
	*
	* @return void
	*/
	protected function processTags()
	{
		if (empty($this->tagStack))
		{
			return;
		}

		// Initialize the count tables
		foreach (array_keys($this->tagsConfig) as $tagName)
		{
			$this->cntOpen[$tagName]  = 0;
			$this->cntTotal[$tagName] = 0;
		}

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

				$this->currentTag = array_pop($this->tagStack);
				$this->processCurrentTag();
			}

			// Close tags that were left open
			foreach ($this->openTags as $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
				$this->addMagicEndTag($startTag, $this->textLen);
			}
		}
		while (!empty($this->tagStack));
	}

	/**
	* Process current tag
	*
	* @return void
	*/
	protected 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 (($this->context['flags'] & self::RULE_IGNORE_TAGS)
		 && !$this->currentTag->canClose(end($this->openTags))
		 && !$this->currentTag->isSystemTag())
		{
			$this->currentTag->invalidate();
		}

		$tagPos = $this->currentTag->getPos();
		$tagLen = $this->currentTag->getLen();

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

			if ($startTag && in_array($startTag, $this->openTags, true))
			{
				// 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
				$this->addEndTag(
					$startTag->getName(),
					$this->pos,
					max(0, $tagPos + $tagLen - $this->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 ($this->currentTag->isIgnoreTag())
			{
				$ignoreLen = $tagPos + $tagLen - $this->pos;

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

					return;
				}
			}

			// Skipped tags are invalidated
			$this->currentTag->invalidate();
		}

		if ($this->currentTag->isInvalid())
		{
			return;
		}

		if ($this->currentTag->isIgnoreTag())
		{
			$this->outputIgnoreTag($this->currentTag);
		}
		elseif ($this->currentTag->isBrTag())
		{
			// Output the tag if it's allowed, ignore it otherwise
			if (!($this->context['flags'] & self::RULE_PREVENT_BR))
			{
				$this->outputBrTag($this->currentTag);
			}
		}
		elseif ($this->currentTag->isParagraphBreak())
		{
			$this->outputText($this->currentTag->getPos(), 0, true);
		}
		elseif ($this->currentTag->isVerbatim())
		{
			$this->outputVerbatim($this->currentTag);
		}
		elseif ($this->currentTag->isStartTag())
		{
			$this->processStartTag($this->currentTag);
		}
		else
		{
			$this->processEndTag($this->currentTag);
		}
	}

	/**
	* Process given start tag (including self-closing tags) at current position
	*
	* @param  Tag  $tag Start tag (including self-closing)
	* @return void
	*/
	protected function processStartTag(Tag $tag)
	{
		$tagName   = $tag->getName();
		$tagConfig = $this->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 ($this->cntTotal[$tagName] >= $tagConfig['tagLimit'])
		{
			$this->logger->err(
				'Tag limit exceeded',
				[
					'tag'      => $tag,
					'tagName'  => $tagName,
					'tagLimit' => $tagConfig['tagLimit']
				]
			);
			$tag->invalidate();

			return;
		}

		FilterProcessing::filterTag($tag, $this, $this->tagsConfig, $this->openTags);
		if ($tag->isInvalid())
		{
			return;
		}

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

		if ($this->cntOpen[$tagName] >= $tagConfig['nestingLimit'])
		{
			$this->logger->err(
				'Nesting limit exceeded',
				[
					'tag'          => $tag,
					'tagName'      => $tagName,
					'nestingLimit' => $tagConfig['nestingLimit']
				]
			);
			$tag->invalidate();

			return;
		}

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

			return;
		}

		if ($this->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 ($tag->getFlags() & self::RULE_AUTO_CLOSE
		 && !$tag->isSelfClosingTag()
		 && !$tag->getEndTag()
		 && !$this->isFollowedByClosingTag($tag))
		{
			$newTag = new Tag(Tag::SELF_CLOSING_TAG, $tagName, $tag->getPos(), $tag->getLen());
			$newTag->setAttributes($tag->getAttributes());
			$newTag->setFlags($tag->getFlags());

			$tag = $newTag;
		}

		if ($tag->getFlags() & self::RULE_TRIM_FIRST_LINE
		 && substr($this->text, $tag->getPos() + $tag->getLen(), 1) === "\n")
		{
			$this->addIgnoreTag($tag->getPos() + $tag->getLen(), 1);
		}

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

		// Apply the createChild rules if applicable
		$this->createChild($tag);
	}

	/**
	* Process given end tag at current position
	*
	* @param  Tag  $tag end tag
	* @return void
	*/
	protected function processEndTag(Tag $tag)
	{
		$tagName = $tag->getName();

		if (empty($this->cntOpen[$tagName]))
		{
			// This is an end tag with no start tag
			return;
		}

		/**
		* @var array List of tags need to be closed before given tag
		*/
		$closeTags = [];

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

			if ($tag->canClose($openTag))
			{
				break;
			}

			$closeTags[] = $openTag;
			++$this->currentFixingCost;
		}

		if ($i < 0)
		{
			// Did not find a matching tag
			$this->logger->debug('Skipping end tag with no start tag', ['tag' => $tag]);

			return;
		}

		// Accumulate flags to determine whether whitespace should be trimmed
		$flags = $tag->getFlags();
		foreach ($closeTags as $openTag)
		{
			$flags |= $openTag->getFlags();
		}
		$ignoreWhitespace = (bool) ($flags & self::RULE_IGNORE_WHITESPACE);

		// Only reopen tags if we haven't exceeded our "fixing" budget
		$keepReopening = (bool) ($this->currentFixingCost < $this->maxFixingCost);

		// Iterate over tags that are being closed, output their end tag and collect tags to be
		// reopened
		$reopenTags = [];
		foreach ($closeTags as $openTag)
		{
			$openTagName = $openTag->getName();

			// Test whether this tag should be reopened automatically
			if ($keepReopening)
			{
				if ($openTag->getFlags() & self::RULE_AUTO_REOPEN)
				{
					$reopenTags[] = $openTag;
				}
				else
				{
					$keepReopening = false;
				}
			}

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

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

		// Output our tag, moving the cursor past it, then update the context
		$this->outputTag($tag);
		$this->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 (!empty($closeTags) && $this->currentFixingCost < $this->maxFixingCost)
		{
			/**
			* @var integer Rightmost position of the portion of text to ignore
			*/
			$ignorePos = $this->pos;

			$i = count($this->tagStack);
			while (--$i >= 0 && ++$this->currentFixingCost < $this->maxFixingCost)
			{
				$upcomingTag = $this->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
				$j = count($closeTags);

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

						if (isset($reopenTags[$j]))
						{
							array_splice($reopenTags, $j, 1);
						}

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

						break;
					}
				}
			}

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

		// Re-add tags that need to be reopened, at current cursor position
		foreach ($reopenTags as $startTag)
		{
			$newTag = $this->addCopyTag($startTag, $this->pos, 0);

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

	/**
	* Update counters and replace current context with its parent context
	*
	* @return void
	*/
	protected function popContext()
	{
		$tag = array_pop($this->openTags);
		--$this->cntOpen[$tag->getName()];
		$this->context = $this->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)
	* @return void
	*/
	protected function pushContext(Tag $tag)
	{
		$tagName   = $tag->getName();
		$tagFlags  = $tag->getFlags();
		$tagConfig = $this->tagsConfig[$tagName];

		++$this->cntTotal[$tagName];

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

		// Recompute the allowed tags
		$allowed = [];
		foreach ($this->context['allowed'] as $k => $v)
		{
			// If the current tag is not transparent, override the low bits (allowed children) of
			// current context with its high bits (allowed descendants)
			if (!($tagFlags & self::RULE_IS_TRANSPARENT))
			{
				$v = ($v & 0xFF00) | ($v >> 8);
			}
			$allowed[] = $tagConfig['allowed'][$k] & $v;
		}

		// Use this tag's flags as a base for this context and add inherited rules
		$flags = $tagFlags | ($this->context['flags'] & self::RULES_INHERITANCE);

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

		++$this->cntOpen[$tagName];
		$this->openTags[] = $tag;
		$this->context = [
			'allowed'       => $allowed,
			'flags'         => $flags,
			'inParagraph'   => false,
			'parentContext' => $this->context
		];
	}

	/**
	* Return whether given tag is allowed in current context
	*
	* @param  string $tagName
	* @return bool
	*/
	protected function tagIsAllowed($tagName)
	{
		$n = $this->tagsConfig[$tagName]['bitNumber'];

		return (bool) ($this->context['allowed'][$n >> 3] & (1 << ($n & 7)));
	}

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

	/**
	* Add a start tag
	*
	* @param  string  $name Name of the tag
	* @param  integer $pos  Position of the tag in the text
	* @param  integer $len  Length of text consumed by the tag
	* @param  integer $prio Tag's priority
	* @return Tag
	*/
	public function addStartTag($name, $pos, $len, $prio = 0)
	{
		return $this->addTag(Tag::START_TAG, $name, $pos, $len, $prio);
	}

	/**
	* Add an end tag
	*
	* @param  string  $name Name of the tag
	* @param  integer $pos  Position of the tag in the text
	* @param  integer $len  Length of text consumed by the tag
	* @param  integer $prio Tag's priority
	* @return Tag
	*/
	public function addEndTag($name, $pos, $len, $prio = 0)
	{
		return $this->addTag(Tag::END_TAG, $name, $pos, $len, $prio);
	}

	/**
	* Add a self-closing tag
	*
	* @param  string  $name Name of the tag
	* @param  integer $pos  Position of the tag in the text
	* @param  integer $len  Length of text consumed by the tag
	* @param  integer $prio Tag's priority
	* @return Tag
	*/
	public function addSelfClosingTag($name, $pos, $len, $prio = 0)
	{
		return $this->addTag(Tag::SELF_CLOSING_TAG, $name, $pos, $len, $prio);
	}

	/**
	* Add a 0-width "br" tag to force a line break at given position
	*
	* @param  integer $pos  Position of the tag in the text
	* @param  integer $prio Tag's priority
	* @return Tag
	*/
	public function addBrTag($pos, $prio = 0)
	{
		return $this->addTag(Tag::SELF_CLOSING_TAG, 'br', $pos, 0, $prio);
	}

	/**
	* Add an "ignore" tag
	*
	* @param  integer $pos  Position of the tag in the text
	* @param  integer $len  Length of text consumed by the tag
	* @param  integer $prio Tag's priority
	* @return Tag
	*/
	public function addIgnoreTag($pos, $len, $prio = 0)
	{
		return $this->addTag(Tag::SELF_CLOSING_TAG, 'i', $pos, min($len, $this->textLen - $pos), $prio);
	}

	/**
	* Add a paragraph break at given position
	*
	* Uses a zero-width tag that is actually never output in the result
	*
	* @param  integer $pos  Position of the tag in the text
	* @param  integer $prio Tag's priority
	* @return Tag
	*/
	public function addParagraphBreak($pos, $prio = 0)
	{
		return $this->addTag(Tag::SELF_CLOSING_TAG, 'pb', $pos, 0, $prio);
	}

	/**
	* Add a copy of given tag at given position and length
	*
	* @param  Tag     $tag  Original tag
	* @param  integer $pos  Copy's position
	* @param  integer $len  Copy's length
	* @param  integer $prio Copy's priority (same as original by default)
	* @return Tag           Copy tag
	*/
	public function addCopyTag(Tag $tag, $pos, $len, $prio = null)
	{
		if (!isset($prio))
		{
			$prio = $tag->getSortPriority();
		}
		$copy = $this->addTag($tag->getType(), $tag->getName(), $pos, $len, $prio);
		$copy->setAttributes($tag->getAttributes());

		return $copy;
	}

	/**
	* Add a tag
	*
	* @param  integer $type Tag's type
	* @param  string  $name Name of the tag
	* @param  integer $pos  Position of the tag in the text
	* @param  integer $len  Length of text consumed by the tag
	* @param  integer $prio Tag's priority
	* @return Tag
	*/
	protected function addTag($type, $name, $pos, $len, $prio)
	{
		// Create the tag
		$tag = new Tag($type, $name, $pos, $len, $prio);

		// Set this tag's rules bitfield
		if (isset($this->tagsConfig[$name]))
		{
			$tag->setFlags($this->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 ((!isset($this->tagsConfig[$name]) && !$tag->isSystemTag())
		 || $this->isInvalidTextSpan($pos, $len))
		{
			$tag->invalidate();
		}
		elseif (!empty($this->tagsConfig[$name]['isDisabled']))
		{
			$this->logger->warn(
				'Tag is disabled',
				[
					'tag'     => $tag,
					'tagName' => $name
				]
			);
			$tag->invalidate();
		}
		else
		{
			$this->insertTag($tag);
		}

		return $tag;
	}

	/**
	* Test whether given text span is outside text boundaries or an invalid UTF sequence
	*
	* @param  integer $pos Start of text
	* @param  integer $len Length of text
	* @return bool
	*/
	protected function isInvalidTextSpan($pos, $len)
	{
		return ($len < 0 || $pos < 0 || $pos + $len > $this->textLen || preg_match('([\\x80-\\xBF])', substr($this->text, $pos, 1) . substr($this->text, $pos + $len, 1)));
	}

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

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

		return $startTag;
	}

	/**
	* Add a tag that represents a verbatim copy of the original text
	*
	* @param  integer $pos  Position of the tag in the text
	* @param  integer $len  Length of text consumed by the tag
	* @param  integer $prio Tag's priority
	* @return Tag
	*/
	public function addVerbatim($pos, $len, $prio = 0)
	{
		return $this->addTag(Tag::SELF_CLOSING_TAG, 'v', $pos, $len, $prio);
	}

	/**
	* Sort tags by position and precedence
	*
	* @return void
	*/
	protected function sortTags()
	{
		$arr = [];
		foreach ($this->tagStack as $i => $tag)
		{
			$key       = $this->getSortKey($tag, $i);
			$arr[$key] = $tag;
		}
		krsort($arr);

		$this->tagStack         = array_values($arr);
		$this->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  integer $tagIndex
	* @return string
	*/
	protected function getSortKey(Tag $tag, int $tagIndex = 0): string
	{
		// Ensure that negative values are sorted correctly by flagging them and making them positive
		$prioFlag = ($tag->getSortPriority() >= 0);
		$prio     = $tag->getSortPriority();
		if (!$prioFlag)
		{
			$prio += (1 << 30);
		}

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

		return sprintf('%8x%d%8x%d%8x%8x', $tag->getPos(), $prioFlag, $prio, $lenFlag, $lenOrder, $tagIndex);
	}
}