[Summary view] [Print] [Text view]

   1  /**#@+
   2  * Boolean rules bitfield
   3  */
   4  /** @const */ var RULE_AUTO_CLOSE        = 1 << 0;
   5  /** @const */ var RULE_AUTO_REOPEN       = 1 << 1;
   6  /** @const */ var RULE_BREAK_PARAGRAPH   = 1 << 2;
   7  /** @const */ var RULE_CREATE_PARAGRAPHS = 1 << 3;
   8  /** @const */ var RULE_DISABLE_AUTO_BR   = 1 << 4;
   9  /** @const */ var RULE_ENABLE_AUTO_BR    = 1 << 5;
  10  /** @const */ var RULE_IGNORE_TAGS       = 1 << 6;
  11  /** @const */ var RULE_IGNORE_TEXT       = 1 << 7;
  12  /** @const */ var RULE_IGNORE_WHITESPACE = 1 << 8;
  13  /** @const */ var RULE_IS_TRANSPARENT    = 1 << 9;
  14  /** @const */ var RULE_PREVENT_BR        = 1 << 10;
  15  /** @const */ var RULE_SUSPEND_AUTO_BR   = 1 << 11;
  16  /** @const */ var RULE_TRIM_FIRST_LINE   = 1 << 12;
  17  /**#@-*/
  18  
  19  /**
  20  * @const Bitwise disjunction of rules related to automatic line breaks
  21  */
  22  var RULES_AUTO_LINEBREAKS = RULE_DISABLE_AUTO_BR | RULE_ENABLE_AUTO_BR | RULE_SUSPEND_AUTO_BR;
  23  
  24  /**
  25  * @const Bitwise disjunction of rules that are inherited by subcontexts
  26  */
  27  var RULES_INHERITANCE = RULE_ENABLE_AUTO_BR;
  28  
  29  /**
  30  * @const All the characters that are considered whitespace
  31  */
  32  var WHITESPACE = " \n\t";
  33  
  34  /**
  35  * @type {!Object.<string,!number>} Number of open tags for each tag name
  36  */
  37  var cntOpen;
  38  
  39  /**
  40  * @type {!Object.<string,!number>} Number of times each tag has been used
  41  */
  42  var cntTotal;
  43  
  44  /**
  45  * @type {!Object} Current context
  46  */
  47  var context;
  48  
  49  /**
  50  * @type {!number} How hard the parser has worked on fixing bad markup so far
  51  */
  52  var currentFixingCost;
  53  
  54  /**
  55  * @type {Tag} Current tag being processed
  56  */
  57  var currentTag;
  58  
  59  /**
  60  * @type {!boolean} Whether the output contains "rich" tags, IOW any tag that is not <p> or <br/>
  61  */
  62  var isRich;
  63  
  64  /**
  65  * @type {!Logger} This parser's logger
  66  */
  67  var logger = new Logger;
  68  
  69  /**
  70  * @type {!number} How hard the parser should work on fixing bad markup
  71  */
  72  var maxFixingCost = 10000;
  73  
  74  /**
  75  * @type {!Object} Associative array of namespace prefixes in use in document (prefixes used as key)
  76  */
  77  var namespaces;
  78  
  79  /**
  80  * @type {!Array.<!Tag>} Stack of open tags (instances of Tag)
  81  */
  82  var openTags;
  83  
  84  /**
  85  * @type {!string} This parser's output
  86  */
  87  var output;
  88  
  89  /**
  90  * @type {!Object.<!Object>}
  91  */
  92  var plugins;
  93  
  94  /**
  95  * @type {!number} Position of the cursor in the original text
  96  */
  97  var pos;
  98  
  99  /**
 100  * @type {!Object} Variables registered for use in filters
 101  */
 102  var registeredVars;
 103  
 104  /**
 105  * @type {!Object} Root context, used at the root of the document
 106  */
 107  var rootContext;
 108  
 109  /**
 110  * @type {!Object} Tags' config
 111  * @const
 112  */
 113  var tagsConfig;
 114  
 115  /**
 116  * @type {!Array.<!Tag>} Tag storage
 117  */
 118  var tagStack;
 119  
 120  /**
 121  * @type {!boolean} Whether the tags in the stack are sorted
 122  */
 123  var tagStackIsSorted;
 124  
 125  /**
 126  * @type {!string} Text being parsed
 127  */
 128  var text;
 129  
 130  /**
 131  * @type {!number} Length of the text being parsed
 132  */
 133  var textLen;
 134  
 135  /**
 136  * @type {!number} Counter incremented everytime the parser is reset. Used to as a canary to detect
 137  *                 whether the parser was reset during execution
 138  */
 139  var uid = 0;
 140  
 141  /**
 142  * @type {!number} Position before which we output text verbatim, without paragraphs or linebreaks
 143  */
 144  var wsPos;
 145  
 146  //==========================================================================
 147  // Public API
 148  //==========================================================================
 149  
 150  /**
 151  * Disable a tag
 152  *
 153  * @param {!string} tagName Name of the tag
 154  */
 155  function disableTag(tagName)
 156  {
 157      if (tagsConfig[tagName])
 158      {
 159          copyTagConfig(tagName).isDisabled = true;
 160      }
 161  }
 162  
 163  /**
 164  * Enable a tag
 165  *
 166  * @param {!string} tagName Name of the tag
 167  */
 168  function enableTag(tagName)
 169  {
 170      if (tagsConfig[tagName])
 171      {
 172          copyTagConfig(tagName).isDisabled = false;
 173      }
 174  }
 175  
 176  /**
 177  * Get this parser's Logger instance
 178  *
 179  * @return {!Logger}
 180  */
 181  function getLogger()
 182  {
 183      return logger;
 184  }
 185  
 186  /**
 187  * Parse a text
 188  *
 189  * @param  {!string} _text Text to parse
 190  * @return {!string}       XML representation
 191  */
 192  function parse(_text)
 193  {
 194      // Reset the parser and save the uid
 195      reset(_text);
 196      var _uid = uid;
 197  
 198      // Do the heavy lifting
 199      executePluginParsers();
 200      processTags();
 201  
 202      // Finalize the document
 203      finalizeOutput();
 204  
 205      // Check the uid in case a plugin or a filter reset the parser mid-execution
 206      if (uid !== _uid)
 207      {
 208          throw 'The parser has been reset during execution';
 209      }
 210  
 211      // Log a warning if the fixing cost limit was exceeded
 212      if (currentFixingCost > maxFixingCost)
 213      {
 214          logger.warn('Fixing cost limit exceeded');
 215      }
 216  
 217      return output;
 218  }
 219  
 220  /**
 221  * Reset the parser for a new parsing
 222  *
 223  * @param {!string} _text Text to be parsed
 224  */
 225  function reset(_text)
 226  {
 227      // Normalize CR/CRLF to LF, remove control characters that aren't allowed in XML
 228      _text = _text.replace(/\r\n?/g, "\n");
 229      _text = _text.replace(/[\x00-\x08\x0B\x0C\x0E-\x1F]+/g, '');
 230  
 231      // Clear the logs
 232      logger.clear();
 233  
 234      // Initialize the rest
 235      cntOpen           = {};
 236      cntTotal          = {};
 237      currentFixingCost = 0;
 238      currentTag        = null;
 239      isRich            = false;
 240      namespaces        = {};
 241      openTags          = [];
 242      output            = '';
 243      pos               = 0;
 244      tagStack          = [];
 245      tagStackIsSorted  = false;
 246      text              = _text;
 247      textLen           = text.length;
 248      wsPos             = 0;
 249  
 250      // Initialize the root context
 251      context = rootContext;
 252      context.inParagraph = false;
 253  
 254      // Bump the UID
 255      ++uid;
 256  }
 257  
 258  /**
 259  * Change a tag's tagLimit
 260  *
 261  * NOTE: the default tagLimit should generally be set during configuration instead
 262  *
 263  * @param {!string} tagName  The tag's name, in UPPERCASE
 264  * @param {!number} tagLimit
 265  */
 266  function setTagLimit(tagName, tagLimit)
 267  {
 268      if (tagsConfig[tagName])
 269      {
 270          copyTagConfig(tagName).tagLimit = tagLimit;
 271      }
 272  }
 273  
 274  /**
 275  * Change a tag's nestingLimit
 276  *
 277  * NOTE: the default nestingLimit should generally be set during configuration instead
 278  *
 279  * @param {!string} tagName      The tag's name, in UPPERCASE
 280  * @param {!number} nestingLimit
 281  */
 282  function setNestingLimit(tagName, nestingLimit)
 283  {
 284      if (tagsConfig[tagName])
 285      {
 286          copyTagConfig(tagName).nestingLimit = nestingLimit;
 287      }
 288  }
 289  
 290  /**
 291  * Copy a tag's config
 292  *
 293  * This method ensures that the tag's config is its own object and not shared with another
 294  * identical tag
 295  *
 296  * @param  {!string} tagName Tag's name
 297  * @return {!Object}         Tag's config
 298  */
 299  function copyTagConfig(tagName)
 300  {
 301      var tagConfig = {}, k;
 302      for (k in tagsConfig[tagName])
 303      {
 304          tagConfig[k] = tagsConfig[tagName][k];
 305      }
 306  
 307      return tagsConfig[tagName] = tagConfig;
 308  }
 309  
 310  //==========================================================================
 311  // Output handling
 312  //==========================================================================
 313  
 314  /**
 315  * Replace Unicode characters outside the BMP with XML entities in the output
 316  */
 317  function encodeUnicodeSupplementaryCharacters()
 318  {
 319      output = output.replace(
 320          /[\uD800-\uDBFF][\uDC00-\uDFFF]/g,
 321          encodeUnicodeSupplementaryCharactersCallback
 322      );
 323  }
 324  
 325  /**
 326  * Encode given surrogate pair into an XML entity
 327  *
 328  * @param  {!string} pair Surrogate pair
 329  * @return {!string}      XML entity
 330  */
 331  function encodeUnicodeSupplementaryCharactersCallback(pair)
 332  {
 333      var cp = (pair.charCodeAt(0) << 10) + pair.charCodeAt(1) - 56613888;
 334  
 335      return '&#' + cp + ';';
 336  }
 337  
 338  /**
 339  * Finalize the output by appending the rest of the unprocessed text and create the root node
 340  */
 341  function finalizeOutput()
 342  {
 343      var tmp;
 344  
 345      // Output the rest of the text and close the last paragraph
 346      outputText(textLen, 0, true);
 347  
 348      // Remove empty tag pairs, e.g. <I><U></U></I> as well as empty paragraphs
 349      do
 350      {
 351          tmp = output;
 352          output = output.replace(/<([^ />]+)[^>]*><\/\1>/g, '');
 353      }
 354      while (output !== tmp);
 355  
 356      // Merge consecutive <i> tags
 357      output = output.replace(/<\/i><i>/g, '');
 358  
 359      // Remove control characters from the output to ensure it's valid XML
 360      output = output.replace(/[\x00-\x08\x0B-\x1F]/g, '');
 361  
 362      // Encode Unicode characters that are outside of the BMP
 363      encodeUnicodeSupplementaryCharacters();
 364  
 365      // Use a <r> root if the text is rich, or <t> for plain text (including <p></p> and <br/>)
 366      var tagName = (isRich) ? 'r' : 't';
 367  
 368      // Prepare the root node with all the namespace declarations
 369      tmp = '<' + tagName;
 370      if (HINT.namespaces)
 371      {
 372          for (var prefix in namespaces)
 373          {
 374              tmp += ' xmlns:' + prefix + '="urn:s9e:TextFormatter:' + prefix + '"';
 375          }
 376      }
 377  
 378      output = tmp + '>' + output + '</' + tagName + '>';
 379  }
 380  
 381  /**
 382  * Append a tag to the output
 383  *
 384  * @param {!Tag} tag Tag to append
 385  */
 386  function outputTag(tag)
 387  {
 388      isRich = true;
 389  
 390      var tagName    = tag.getName(),
 391          tagPos     = tag.getPos(),
 392          tagLen     = tag.getLen(),
 393          tagFlags   = tag.getFlags(),
 394          skipBefore = 0,
 395          skipAfter  = 0;
 396  
 397      if (HINT.RULE_IGNORE_WHITESPACE && (tagFlags & RULE_IGNORE_WHITESPACE))
 398      {
 399          skipBefore = 1;
 400          skipAfter  = (tag.isEndTag()) ? 2 : 1;
 401      }
 402  
 403      // Current paragraph must end before the tag if:
 404      //  - the tag is a start (or self-closing) tag and it breaks paragraphs, or
 405      //  - the tag is an end tag (but not self-closing)
 406      var closeParagraph = false;
 407      if (tag.isStartTag())
 408      {
 409          if (HINT.RULE_BREAK_PARAGRAPH && (tagFlags & RULE_BREAK_PARAGRAPH))
 410          {
 411              closeParagraph = true;
 412          }
 413      }
 414      else
 415      {
 416          closeParagraph = true;
 417      }
 418  
 419      // Let the cursor catch up with this tag's position
 420      outputText(tagPos, skipBefore, closeParagraph);
 421  
 422      // Capture the text consumed by the tag
 423      var tagText = (tagLen)
 424                  ? htmlspecialchars_noquotes(text.substr(tagPos, tagLen))
 425                  : '';
 426  
 427      // Output current tag
 428      if (tag.isStartTag())
 429      {
 430          // Handle paragraphs before opening the tag
 431          if (!HINT.RULE_BREAK_PARAGRAPH || !(tagFlags & RULE_BREAK_PARAGRAPH))
 432          {
 433              outputParagraphStart(tagPos);
 434          }
 435  
 436          // Record this tag's namespace, if applicable
 437          if (HINT.namespaces)
 438          {
 439              var colonPos = tagName.indexOf(':');
 440              if (colonPos > 0)
 441              {
 442                  namespaces[tagName.substr(0, colonPos)] = 0;
 443              }
 444          }
 445  
 446          // Open the start tag and add its attributes, but don't close the tag
 447          output += '<' + tagName;
 448  
 449          // We output the attributes in lexical order. Helps canonicalizing the output and could
 450          // prove useful someday
 451          var attributes = tag.getAttributes(),
 452              attributeNames = [];
 453          for (var attrName in attributes)
 454          {
 455              attributeNames.push(attrName);
 456          }
 457          attributeNames.sort(
 458              function(a, b)
 459              {
 460                  return (a > b) ? 1 : -1;
 461              }
 462          );
 463          attributeNames.forEach(
 464              function(attrName)
 465              {
 466                  output += ' ' + attrName + '="' + htmlspecialchars_compat(attributes[attrName].toString()).replace(/\n/g, '&#10;') + '"';
 467              }
 468          );
 469  
 470          if (tag.isSelfClosingTag())
 471          {
 472              if (tagLen)
 473              {
 474                  output += '>' + tagText + '</' + tagName + '>';
 475              }
 476              else
 477              {
 478                  output += '/>';
 479              }
 480          }
 481          else if (tagLen)
 482          {
 483              output += '><s>' + tagText + '</s>';
 484          }
 485          else
 486          {
 487              output += '>';
 488          }
 489      }
 490      else
 491      {
 492          if (tagLen)
 493          {
 494              output += '<e>' + tagText + '</e>';
 495          }
 496  
 497          output += '</' + tagName + '>';
 498      }
 499  
 500      // Move the cursor past the tag
 501      pos = tagPos + tagLen;
 502  
 503      // Skip newlines (no other whitespace) after this tag
 504      wsPos = pos;
 505      while (skipAfter && wsPos < textLen && text[wsPos] === "\n")
 506      {
 507          // Decrement the number of lines to skip
 508          --skipAfter;
 509  
 510          // Move the cursor past the newline
 511          ++wsPos;
 512      }
 513  }
 514  
 515  /**
 516  * Output the text between the cursor's position (included) and given position (not included)
 517  *
 518  * @param  {!number}  catchupPos     Position we're catching up to
 519  * @param  {!number}  maxLines       Maximum number of lines to ignore at the end of the text
 520  * @param  {!boolean} closeParagraph Whether to close the paragraph at the end, if applicable
 521  */
 522  function outputText(catchupPos, maxLines, closeParagraph)
 523  {
 524      if (closeParagraph)
 525      {
 526          if (!(context.flags & RULE_CREATE_PARAGRAPHS))
 527          {
 528              closeParagraph = false;
 529          }
 530          else
 531          {
 532              // Ignore any number of lines at the end if we're closing a paragraph
 533              maxLines = -1;
 534          }
 535      }
 536  
 537      if (pos >= catchupPos)
 538      {
 539          // We're already there, close the paragraph if applicable and return
 540          if (closeParagraph)
 541          {
 542              outputParagraphEnd();
 543          }
 544      }
 545  
 546      // Skip over previously identified whitespace if applicable
 547      if (wsPos > pos)
 548      {
 549          var skipPos = Math.min(catchupPos, wsPos);
 550          output += text.substr(pos, skipPos - pos);
 551          pos = skipPos;
 552  
 553          if (pos >= catchupPos)
 554          {
 555              // Skipped everything. Close the paragraph if applicable and return
 556              if (closeParagraph)
 557              {
 558                  outputParagraphEnd();
 559              }
 560          }
 561      }
 562  
 563      var catchupLen, catchupText;
 564  
 565      // Test whether we're even supposed to output anything
 566      if (HINT.RULE_IGNORE_TEXT && context.flags & RULE_IGNORE_TEXT)
 567      {
 568          catchupLen  = catchupPos - pos,
 569          catchupText = text.substr(pos, catchupLen);
 570  
 571          // If the catchup text is not entirely composed of whitespace, we put it inside ignore tags
 572          if (!/^[ \n\t]*$/.test(catchupText))
 573          {
 574              catchupText = '<i>' + htmlspecialchars_noquotes(catchupText) + '</i>';
 575          }
 576  
 577          output += catchupText;
 578          pos = catchupPos;
 579  
 580          if (closeParagraph)
 581          {
 582              outputParagraphEnd();
 583          }
 584  
 585          return;
 586      }
 587  
 588      // Compute the amount of text to ignore at the end of the output
 589      var ignorePos = catchupPos,
 590          ignoreLen = 0;
 591  
 592      // Ignore as many lines (including whitespace) as specified
 593      while (maxLines && --ignorePos >= pos)
 594      {
 595          var c = text[ignorePos];
 596          if (c !== ' ' && c !== "\n" && c !== "\t")
 597          {
 598              break;
 599          }
 600  
 601          if (c === "\n")
 602          {
 603              --maxLines;
 604          }
 605  
 606          ++ignoreLen;
 607      }
 608  
 609      // Adjust catchupPos to ignore the text at the end
 610      catchupPos -= ignoreLen;
 611  
 612      // Break down the text in paragraphs if applicable
 613      if (HINT.RULE_CREATE_PARAGRAPHS && context.flags & RULE_CREATE_PARAGRAPHS)
 614      {
 615          if (!context.inParagraph)
 616          {
 617              outputWhitespace(catchupPos);
 618  
 619              if (catchupPos > pos)
 620              {
 621                  outputParagraphStart(catchupPos);
 622              }
 623          }
 624  
 625          // Look for a paragraph break in this text
 626          var pbPos = text.indexOf("\n\n", pos);
 627  
 628          while (pbPos > -1 && pbPos < catchupPos)
 629          {
 630              outputText(pbPos, 0, true);
 631              outputParagraphStart(catchupPos);
 632  
 633              pbPos = text.indexOf("\n\n", pos);
 634          }
 635      }
 636  
 637      // Capture, escape and output the text
 638      if (catchupPos > pos)
 639      {
 640          catchupText = htmlspecialchars_noquotes(
 641              text.substr(pos, catchupPos - pos)
 642          );
 643  
 644          // Format line breaks if applicable
 645          if (HINT.RULE_ENABLE_AUTO_BR && (context.flags & RULES_AUTO_LINEBREAKS) === RULE_ENABLE_AUTO_BR)
 646          {
 647              catchupText = catchupText.replace(/\n/g, "<br/>\n");
 648          }
 649  
 650          output += catchupText;
 651      }
 652  
 653      // Close the paragraph if applicable
 654      if (closeParagraph)
 655      {
 656          outputParagraphEnd();
 657      }
 658  
 659      // Add the ignored text if applicable
 660      if (ignoreLen)
 661      {
 662          output += text.substr(catchupPos, ignoreLen);
 663      }
 664  
 665      // Move the cursor past the text
 666      pos = catchupPos + ignoreLen;
 667  }
 668  
 669  /**
 670  * Output a linebreak tag
 671  *
 672  * @param  {!Tag} tag
 673  * @return void
 674  */
 675  function outputBrTag(tag)
 676  {
 677      outputText(tag.getPos(), 0, false);
 678      output += '<br/>';
 679  }
 680  
 681  /**
 682  * Output an ignore tag
 683  *
 684  * @param  {!Tag} tag
 685  * @return void
 686  */
 687  function outputIgnoreTag(tag)
 688  {
 689      var tagPos = tag.getPos(),
 690          tagLen = tag.getLen();
 691  
 692      // Capture the text to ignore
 693      var ignoreText = text.substr(tagPos, tagLen);
 694  
 695      // Catch up with the tag's position then output the tag
 696      outputText(tagPos, 0, false);
 697      output += '<i>' + htmlspecialchars_noquotes(ignoreText) + '</i>';
 698      isRich = true;
 699  
 700      // Move the cursor past this tag
 701      pos = tagPos + tagLen;
 702  }
 703  
 704  /**
 705  * Start a paragraph between current position and given position, if applicable
 706  *
 707  * @param  {!number} maxPos Rightmost position at which the paragraph can be opened
 708  */
 709  function outputParagraphStart(maxPos)
 710  {
 711      if (!HINT.RULE_CREATE_PARAGRAPHS)
 712      {
 713          return;
 714      }
 715  
 716      // Do nothing if we're already in a paragraph, or if we don't use paragraphs
 717      if (context.inParagraph
 718       || !(context.flags & RULE_CREATE_PARAGRAPHS))
 719      {
 720          return;
 721      }
 722  
 723      // Output the whitespace between pos and maxPos if applicable
 724      outputWhitespace(maxPos);
 725  
 726      // Open the paragraph, but only if it's not at the very end of the text
 727      if (pos < textLen)
 728      {
 729          output += '<p>';
 730          context.inParagraph = true;
 731      }
 732  }
 733  
 734  /**
 735  * Close current paragraph at current position if applicable
 736  */
 737  function outputParagraphEnd()
 738  {
 739      // Do nothing if we're not in a paragraph
 740      if (!context.inParagraph)
 741      {
 742          return;
 743      }
 744  
 745      output += '</p>';
 746      context.inParagraph = false;
 747  }
 748  
 749  /**
 750  * Output the content of a verbatim tag
 751  *
 752  * @param {!Tag} tag
 753  */
 754  function outputVerbatim(tag)
 755  {
 756      var flags = context.flags;
 757      context.flags = tag.getFlags();
 758      outputText(currentTag.getPos() + currentTag.getLen(), 0, false);
 759      context.flags = flags;
 760  }
 761  
 762  /**
 763  * Skip as much whitespace after current position as possible
 764  *
 765  * @param  {!number} maxPos Rightmost character to be skipped
 766  */
 767  function outputWhitespace(maxPos)
 768  {
 769      while (pos < maxPos && " \n\t".indexOf(text[pos]) > -1)
 770      {
 771          output += text[pos];
 772          ++pos;
 773      }
 774  }
 775  
 776  //==========================================================================
 777  // Plugins handling
 778  //==========================================================================
 779  
 780  /**
 781  * Disable a plugin
 782  *
 783  * @param {!string} pluginName Name of the plugin
 784  */
 785  function disablePlugin(pluginName)
 786  {
 787      if (plugins[pluginName])
 788      {
 789          plugins[pluginName].isDisabled = true;
 790      }
 791  }
 792  
 793  /**
 794  * Enable a plugin
 795  *
 796  * @param {!string} pluginName Name of the plugin
 797  */
 798  function enablePlugin(pluginName)
 799  {
 800      if (plugins[pluginName])
 801      {
 802          plugins[pluginName].isDisabled = false;
 803      }
 804  }
 805  
 806  /**
 807  * Execute given plugin
 808  *
 809  * @param {!string} pluginName Plugin's name
 810  */
 811  function executePluginParser(pluginName)
 812  {
 813      var pluginConfig = plugins[pluginName];
 814      if (pluginConfig.quickMatch && text.indexOf(pluginConfig.quickMatch) < 0)
 815      {
 816          return;
 817      }
 818  
 819      var matches = [];
 820      if (pluginConfig.regexp)
 821      {
 822          matches = getMatches(pluginConfig.regexp, pluginConfig.regexpLimit);
 823          if (!matches.length)
 824          {
 825              return;
 826          }
 827      }
 828  
 829      // Execute the plugin's parser, which will add tags via addStartTag() and others
 830      getPluginParser(pluginName)(text, matches);
 831  }
 832  
 833  /**
 834  * Execute all the plugins
 835  */
 836  function executePluginParsers()
 837  {
 838      for (var pluginName in plugins)
 839      {
 840          if (!plugins[pluginName].isDisabled)
 841          {
 842              executePluginParser(pluginName);
 843          }
 844      }
 845  }
 846  
 847  /**
 848  * Get regexp matches in a manner similar to preg_match_all() with PREG_SET_ORDER | PREG_OFFSET_CAPTURE
 849  *
 850  * @param  {!RegExp} regexp
 851  * @param  {!number} limit
 852  * @return {!Array.<!Array>}
 853  */
 854  function getMatches(regexp, limit)
 855  {
 856      // Reset the regexp
 857      regexp.lastIndex = 0;
 858      var matches = [], cnt = 0, m;
 859      while (++cnt <= limit && (m = regexp.exec(text)))
 860      {
 861          // NOTE: coercing m.index to a number because Closure Compiler thinks pos is a string otherwise
 862          var pos   = +m['index'],
 863              match = [[m[0], pos]],
 864              i = 0;
 865          while (++i < m.length)
 866          {
 867              var str = m[i];
 868  
 869              // Sub-expressions that were not evaluated return undefined
 870              if (str === undefined)
 871              {
 872                  match.push(['', -1]);
 873              }
 874              else
 875              {
 876                  match.push([str, text.indexOf(str, pos)]);
 877                  pos += str.length;
 878              }
 879          }
 880  
 881          matches.push(match);
 882      }
 883  
 884      return matches;
 885  }
 886  
 887  /**
 888  * Get the callback for given plugin's parser
 889  *
 890  * @param  {!string}   pluginName
 891  * @return {!function(string, Array)}
 892  */
 893  function getPluginParser(pluginName)
 894  {
 895      return plugins[pluginName].parser;
 896  }
 897  
 898  /**
 899  * Register a parser
 900  *
 901  * Can be used to add a new parser with no plugin config, or pre-generate a parser for an
 902  * existing plugin
 903  *
 904  * @param  {!string}   pluginName
 905  * @param  {!Function} parser
 906  * @param  {RegExp}   regexp
 907  * @param  {number}   limit
 908  */
 909  function registerParser(pluginName, parser, regexp, limit)
 910  {
 911      // Create an empty config for this plugin to ensure it is executed
 912      if (!plugins[pluginName])
 913      {
 914          plugins[pluginName] = {};
 915      }
 916      if (regexp)
 917      {
 918          plugins[pluginName].regexp = regexp;
 919          plugins[pluginName].limit  = limit || Infinity;
 920      }
 921      plugins[pluginName].parser = parser;
 922  }
 923  
 924  //==========================================================================
 925  // Rules handling
 926  //==========================================================================
 927  
 928  /**
 929  * Apply closeAncestor rules associated with given tag
 930  *
 931  * @param  {!Tag}     tag Tag
 932  * @return {!boolean}     Whether a new tag has been added
 933  */
 934  function closeAncestor(tag)
 935  {
 936      if (!HINT.closeAncestor)
 937      {
 938          return false;
 939      }
 940  
 941      if (openTags.length)
 942      {
 943          var tagName   = tag.getName(),
 944              tagConfig = tagsConfig[tagName];
 945  
 946          if (tagConfig.rules.closeAncestor)
 947          {
 948              var i = openTags.length;
 949  
 950              while (--i >= 0)
 951              {
 952                  var ancestor     = openTags[i],
 953                      ancestorName = ancestor.getName();
 954  
 955                  if (tagConfig.rules.closeAncestor[ancestorName])
 956                  {
 957                      ++currentFixingCost;
 958  
 959                      // We have to close this ancestor. First we reinsert this tag...
 960                      tagStack.push(tag);
 961  
 962                      // ...then we add a new end tag for it with a better priority
 963                      addMagicEndTag(ancestor, tag.getPos(), tag.getSortPriority() - 1);
 964  
 965                      return true;
 966                  }
 967              }
 968          }
 969      }
 970  
 971      return false;
 972  }
 973  
 974  /**
 975  * Apply closeParent rules associated with given tag
 976  *
 977  * @param  {!Tag}     tag Tag
 978  * @return {!boolean}     Whether a new tag has been added
 979  */
 980  function closeParent(tag)
 981  {
 982      if (!HINT.closeParent)
 983      {
 984          return false;
 985      }
 986  
 987      if (openTags.length)
 988      {
 989          var tagName   = tag.getName(),
 990              tagConfig = tagsConfig[tagName];
 991  
 992          if (tagConfig.rules.closeParent)
 993          {
 994              var parent     = openTags[openTags.length - 1],
 995                  parentName = parent.getName();
 996  
 997              if (tagConfig.rules.closeParent[parentName])
 998              {
 999                  ++currentFixingCost;
1000  
1001                  // We have to close that parent. First we reinsert the tag...
1002                  tagStack.push(tag);
1003  
1004                  // ...then we add a new end tag for it with a better priority
1005                  addMagicEndTag(parent, tag.getPos(), tag.getSortPriority() - 1);
1006  
1007                  return true;
1008              }
1009          }
1010      }
1011  
1012      return false;
1013  }
1014  
1015  /**
1016  * Apply the createChild rules associated with given tag
1017  *
1018  * @param {!Tag} tag Tag
1019  */
1020  function createChild(tag)
1021  {
1022      if (!HINT.createChild)
1023      {
1024          return;
1025      }
1026  
1027      var tagConfig = tagsConfig[tag.getName()];
1028      if (tagConfig.rules.createChild)
1029      {
1030          var priority = -1000,
1031              _text    = text.substr(pos),
1032              tagPos   = pos + _text.length - _text.replace(/^[ \n\r\t]+/, '').length;
1033          tagConfig.rules.createChild.forEach(function(tagName)
1034          {
1035              addStartTag(tagName, tagPos, 0, ++priority);
1036          });
1037      }
1038  }
1039  
1040  /**
1041  * Apply fosterParent rules associated with given tag
1042  *
1043  * NOTE: this rule has the potential for creating an unbounded loop, either if a tag tries to
1044  *       foster itself or two or more tags try to foster each other in a loop. We mitigate the
1045  *       risk by preventing a tag from creating a child of itself (the parent still gets closed)
1046  *       and by checking and increasing the currentFixingCost so that a loop of multiple tags
1047  *       do not run indefinitely. The default tagLimit and nestingLimit also serve to prevent the
1048  *       loop from running indefinitely
1049  *
1050  * @param  {!Tag}     tag Tag
1051  * @return {!boolean}     Whether a new tag has been added
1052  */
1053  function fosterParent(tag)
1054  {
1055      if (!HINT.fosterParent)
1056      {
1057          return false;
1058      }
1059  
1060      if (openTags.length)
1061      {
1062          var tagName   = tag.getName(),
1063              tagConfig = tagsConfig[tagName];
1064  
1065          if (tagConfig.rules.fosterParent)
1066          {
1067              var parent     = openTags[openTags.length - 1],
1068                  parentName = parent.getName();
1069  
1070              if (tagConfig.rules.fosterParent[parentName])
1071              {
1072                  if (parentName !== tagName && currentFixingCost < maxFixingCost)
1073                  {
1074                      addFosterTag(tag, parent)
1075                  }
1076  
1077                  // Reinsert current tag
1078                  tagStack.push(tag);
1079  
1080                  // And finally close its parent with a priority that ensures it is processed
1081                  // before this tag
1082                  addMagicEndTag(parent, tag.getPos(), tag.getSortPriority() - 1);
1083  
1084                  // Adjust the fixing cost to account for the additional tags/processing
1085                  currentFixingCost += 4;
1086  
1087                  return true;
1088              }
1089          }
1090      }
1091  
1092      return false;
1093  }
1094  
1095  /**
1096  * Apply requireAncestor rules associated with given tag
1097  *
1098  * @param  {!Tag}     tag Tag
1099  * @return {!boolean}     Whether this tag has an unfulfilled requireAncestor requirement
1100  */
1101  function requireAncestor(tag)
1102  {
1103      if (!HINT.requireAncestor)
1104      {
1105          return false;
1106      }
1107  
1108      var tagName   = tag.getName(),
1109          tagConfig = tagsConfig[tagName];
1110  
1111      if (tagConfig.rules.requireAncestor)
1112      {
1113          var i = tagConfig.rules.requireAncestor.length;
1114          while (--i >= 0)
1115          {
1116              var ancestorName = tagConfig.rules.requireAncestor[i];
1117              if (cntOpen[ancestorName])
1118              {
1119                  return false;
1120              }
1121          }
1122  
1123          logger.err('Tag requires an ancestor', {
1124              'requireAncestor' : tagConfig.rules.requireAncestor.join(', '),
1125              'tag'             : tag
1126          });
1127  
1128          return true;
1129      }
1130  
1131      return false;
1132  }
1133  
1134  //==========================================================================
1135  // Tag processing
1136  //==========================================================================
1137  
1138  /**
1139  * Create and add a copy of a tag as a child of a given tag
1140  *
1141  * @param {!Tag} tag       Current tag
1142  * @param {!Tag} fosterTag Tag to foster
1143  */
1144  function addFosterTag(tag, fosterTag)
1145  {
1146      var coords    = getMagicStartCoords(tag.getPos() + tag.getLen()),
1147          childPos  = coords[0],
1148          childPrio = coords[1];
1149  
1150      // Add a 0-width copy of the parent tag after this tag and make it depend on this tag
1151      var childTag = addCopyTag(fosterTag, childPos, 0, childPrio);
1152      tag.cascadeInvalidationTo(childTag);
1153  }
1154  
1155  /**
1156  * Create and add an end tag for given start tag at given position
1157  *
1158  * @param  {!Tag}    startTag Start tag
1159  * @param  {!number} tagPos   End tag's position (will be adjusted for whitespace if applicable)
1160  * @param  {number=} prio     End tag's priority
1161  * @return {!Tag}
1162  */
1163  function addMagicEndTag(startTag, tagPos, prio)
1164  {
1165      var tagName = startTag.getName();
1166  
1167      // Adjust the end tag's position if whitespace is to be minimized
1168      if (HINT.RULE_IGNORE_WHITESPACE && ((currentTag.getFlags() | startTag.getFlags()) & RULE_IGNORE_WHITESPACE))
1169      {
1170          tagPos = getMagicEndPos(tagPos);
1171      }
1172  
1173      // Add a 0-width end tag that is paired with the given start tag
1174      var endTag = addEndTag(tagName, tagPos, 0, prio || 0);
1175      endTag.pairWith(startTag);
1176  
1177      return endTag;
1178  }
1179  
1180  /**
1181  * Compute the position of a magic end tag, adjusted for whitespace
1182  *
1183  * @param  {!number} tagPos Rightmost possible position for the tag
1184  * @return {!number}
1185  */
1186  function getMagicEndPos(tagPos)
1187  {
1188      // Back up from given position to the cursor's position until we find a character that
1189      // is not whitespace
1190      while (tagPos > pos && WHITESPACE.indexOf(text[tagPos - 1]) > -1)
1191      {
1192          --tagPos;
1193      }
1194  
1195      return tagPos;
1196  }
1197  
1198  /**
1199  * Compute the position and priority of a magic start tag, adjusted for whitespace
1200  *
1201  * @param  {!number} tagPos Leftmost possible position for the tag
1202  * @return {!Array}         [Tag pos, priority]
1203  */
1204  function getMagicStartCoords(tagPos)
1205  {
1206      var nextPos, nextPrio, nextTag, prio;
1207      if (!tagStack.length)
1208      {
1209          // Set the next position outside the text boundaries
1210          nextPos  = textLen + 1;
1211          nextPrio = 0;
1212      }
1213      else
1214      {
1215          nextTag  = tagStack[tagStack.length - 1];
1216          nextPos  = nextTag.getPos();
1217          nextPrio = nextTag.getSortPriority();
1218      }
1219  
1220      // Find the first non-whitespace position before next tag or the end of text
1221      while (tagPos < nextPos && WHITESPACE.indexOf(text[tagPos]) > -1)
1222      {
1223          ++tagPos;
1224      }
1225  
1226      // Set a priority that ensures this tag appears before the next tag
1227      prio = (tagPos === nextPos) ? nextPrio - 1 : 0;
1228  
1229      return [tagPos, prio];
1230  }
1231  
1232  /**
1233  * Test whether given start tag is immediately followed by a closing tag
1234  *
1235  * @param  {!Tag} tag Start tag (including self-closing)
1236  * @return {!boolean}
1237  */
1238  function isFollowedByClosingTag(tag)
1239  {
1240      return (!tagStack.length) ? false : tagStack[tagStack.length - 1].canClose(tag);
1241  }
1242  
1243  /**
1244  * Process all tags in the stack
1245  */
1246  function processTags()
1247  {
1248      if (!tagStack.length)
1249      {
1250          return;
1251      }
1252  
1253      // Initialize the count tables
1254      for (var tagName in tagsConfig)
1255      {
1256          cntOpen[tagName]  = 0;
1257          cntTotal[tagName] = 0;
1258      }
1259  
1260      // Process the tag stack, close tags that were left open and repeat until done
1261      do
1262      {
1263          while (tagStack.length)
1264          {
1265              if (!tagStackIsSorted)
1266              {
1267                  sortTags();
1268              }
1269  
1270              currentTag = tagStack.pop();
1271              processCurrentTag();
1272          }
1273  
1274          // Close tags that were left open
1275          openTags.forEach(function (startTag)
1276          {
1277              // NOTE: we add tags in hierarchical order (ancestors to descendants) but since
1278              //       the stack is processed in LIFO order, it means that tags get closed in
1279              //       the correct order, from descendants to ancestors
1280              addMagicEndTag(startTag, textLen);
1281          });
1282      }
1283      while (tagStack.length);
1284  }
1285  
1286  /**
1287  * Process current tag
1288  */
1289  function processCurrentTag()
1290  {
1291      // Invalidate current tag if tags are disabled and current tag would not close the last open
1292      // tag and is not a system tag
1293      if ((context.flags & RULE_IGNORE_TAGS)
1294       && !currentTag.canClose(openTags[openTags.length - 1])
1295       && !currentTag.isSystemTag())
1296      {
1297          currentTag.invalidate();
1298      }
1299  
1300      var tagPos = currentTag.getPos(),
1301          tagLen = currentTag.getLen();
1302  
1303      // Test whether the cursor passed this tag's position already
1304      if (pos > tagPos && !currentTag.isInvalid())
1305      {
1306          // Test whether this tag is paired with a start tag and this tag is still open
1307          var startTag = currentTag.getStartTag();
1308  
1309          if (startTag && openTags.indexOf(startTag) >= 0)
1310          {
1311              // Create an end tag that matches current tag's start tag, which consumes as much of
1312              // the same text as current tag and is paired with the same start tag
1313              addEndTag(
1314                  startTag.getName(),
1315                  pos,
1316                  Math.max(0, tagPos + tagLen - pos)
1317              ).pairWith(startTag);
1318  
1319              // Note that current tag is not invalidated, it's merely replaced
1320              return;
1321          }
1322  
1323          // If this is an ignore tag, try to ignore as much as the remaining text as possible
1324          if (currentTag.isIgnoreTag())
1325          {
1326              var ignoreLen = tagPos + tagLen - pos;
1327  
1328              if (ignoreLen > 0)
1329              {
1330                  // Create a new ignore tag and move on
1331                  addIgnoreTag(pos, ignoreLen);
1332  
1333                  return;
1334              }
1335          }
1336  
1337          // Skipped tags are invalidated
1338          currentTag.invalidate();
1339      }
1340  
1341      if (currentTag.isInvalid())
1342      {
1343          return;
1344      }
1345  
1346      if (currentTag.isIgnoreTag())
1347      {
1348          outputIgnoreTag(currentTag);
1349      }
1350      else if (currentTag.isBrTag())
1351      {
1352          // Output the tag if it's allowed, ignore it otherwise
1353          if (!HINT.RULE_PREVENT_BR || !(context.flags & RULE_PREVENT_BR))
1354          {
1355              outputBrTag(currentTag);
1356          }
1357      }
1358      else if (currentTag.isParagraphBreak())
1359      {
1360          outputText(currentTag.getPos(), 0, true);
1361      }
1362      else if (currentTag.isVerbatim())
1363      {
1364          outputVerbatim(currentTag);
1365      }
1366      else if (currentTag.isStartTag())
1367      {
1368          processStartTag(currentTag);
1369      }
1370      else
1371      {
1372          processEndTag(currentTag);
1373      }
1374  }
1375  
1376  /**
1377  * Process given start tag (including self-closing tags) at current position
1378  *
1379  * @param {!Tag} tag Start tag (including self-closing)
1380  */
1381  function processStartTag(tag)
1382  {
1383      var tagName   = tag.getName(),
1384          tagConfig = tagsConfig[tagName];
1385  
1386      // 1. Check that this tag has not reached its global limit tagLimit
1387      // 2. Execute this tag's filterChain, which will filter/validate its attributes
1388      // 3. Apply closeParent, closeAncestor and fosterParent rules
1389      // 4. Check for nestingLimit
1390      // 5. Apply requireAncestor rules
1391      //
1392      // This order ensures that the tag is valid and within the set limits before we attempt to
1393      // close parents or ancestors. We need to close ancestors before we can check for nesting
1394      // limits, whether this tag is allowed within current context (the context may change
1395      // as ancestors are closed) or whether the required ancestors are still there (they might
1396      // have been closed by a rule.)
1397      if (cntTotal[tagName] >= tagConfig.tagLimit)
1398      {
1399          logger.err(
1400              'Tag limit exceeded',
1401              {
1402                  'tag'      : tag,
1403                  'tagName'  : tagName,
1404                  'tagLimit' : tagConfig.tagLimit
1405              }
1406          );
1407          tag.invalidate();
1408  
1409          return;
1410      }
1411  
1412      filterTag(tag);
1413      if (tag.isInvalid())
1414      {
1415          return;
1416      }
1417  
1418      if (currentFixingCost < maxFixingCost)
1419      {
1420          if (fosterParent(tag) || closeParent(tag) || closeAncestor(tag))
1421          {
1422              // This tag parent/ancestor needs to be closed, we just return (the tag is still valid)
1423              return;
1424          }
1425      }
1426  
1427      if (cntOpen[tagName] >= tagConfig.nestingLimit)
1428      {
1429          logger.err(
1430              'Nesting limit exceeded',
1431              {
1432                  'tag'          : tag,
1433                  'tagName'      : tagName,
1434                  'nestingLimit' : tagConfig.nestingLimit
1435              }
1436          );
1437          tag.invalidate();
1438  
1439          return;
1440      }
1441  
1442      if (!tagIsAllowed(tagName))
1443      {
1444          var msg     = 'Tag is not allowed in this context',
1445              context = {'tag': tag, 'tagName': tagName};
1446          if (tag.getLen() > 0)
1447          {
1448              logger.warn(msg, context);
1449          }
1450          else
1451          {
1452              logger.debug(msg, context);
1453          }
1454          tag.invalidate();
1455  
1456          return;
1457      }
1458  
1459      if (requireAncestor(tag))
1460      {
1461          tag.invalidate();
1462  
1463          return;
1464      }
1465  
1466      // If this tag has an autoClose rule and it's not paired with an end tag or followed by an
1467      // end tag, we replace it with a self-closing tag with the same properties
1468      if (HINT.RULE_AUTO_CLOSE
1469       && tag.getFlags() & RULE_AUTO_CLOSE
1470       && !tag.getEndTag()
1471       && !isFollowedByClosingTag(tag))
1472      {
1473          var newTag = new Tag(Tag.SELF_CLOSING_TAG, tagName, tag.getPos(), tag.getLen());
1474          newTag.setAttributes(tag.getAttributes());
1475          newTag.setFlags(tag.getFlags());
1476  
1477          tag = newTag;
1478      }
1479  
1480      if (HINT.RULE_TRIM_FIRST_LINE
1481       && tag.getFlags() & RULE_TRIM_FIRST_LINE
1482       && !tag.getEndTag()
1483       && text[tag.getPos() + tag.getLen()] === "\n")
1484      {
1485          addIgnoreTag(tag.getPos() + tag.getLen(), 1);
1486      }
1487  
1488      // This tag is valid, output it and update the context
1489      outputTag(tag);
1490      pushContext(tag);
1491  
1492      // Apply the createChild rules if applicable
1493      createChild(tag);
1494  }
1495  
1496  /**
1497  * Process given end tag at current position
1498  *
1499  * @param {!Tag} tag End tag
1500  */
1501  function processEndTag(tag)
1502  {
1503      var tagName = tag.getName();
1504  
1505      if (!cntOpen[tagName])
1506      {
1507          // This is an end tag with no start tag
1508          return;
1509      }
1510  
1511      /**
1512      * @type {!Array.<!Tag>} List of tags need to be closed before given tag
1513      */
1514      var closeTags = [];
1515  
1516      // Iterate through all open tags from last to first to find a match for our tag
1517      var i = openTags.length;
1518      while (--i >= 0)
1519      {
1520          var openTag = openTags[i];
1521  
1522          if (tag.canClose(openTag))
1523          {
1524              break;
1525          }
1526  
1527          closeTags.push(openTag);
1528          ++currentFixingCost;
1529      }
1530  
1531      if (i < 0)
1532      {
1533          // Did not find a matching tag
1534          logger.debug('Skipping end tag with no start tag', {'tag': tag});
1535  
1536          return;
1537      }
1538  
1539      // Accumulate flags to determine whether whitespace should be trimmed
1540      var flags = tag.getFlags();
1541      closeTags.forEach(function(openTag)
1542      {
1543          flags |= openTag.getFlags();
1544      });
1545      var ignoreWhitespace = (HINT.RULE_IGNORE_WHITESPACE && (flags & RULE_IGNORE_WHITESPACE));
1546  
1547      // Only reopen tags if we haven't exceeded our "fixing" budget
1548      var keepReopening = HINT.RULE_AUTO_REOPEN && (currentFixingCost < maxFixingCost),
1549          reopenTags    = [];
1550      closeTags.forEach(function(openTag)
1551      {
1552          var openTagName = openTag.getName();
1553  
1554          // Test whether this tag should be reopened automatically
1555          if (keepReopening)
1556          {
1557              if (openTag.getFlags() & RULE_AUTO_REOPEN)
1558              {
1559                  reopenTags.push(openTag);
1560              }
1561              else
1562              {
1563                  keepReopening = false;
1564              }
1565          }
1566  
1567          // Find the earliest position we can close this open tag
1568          var tagPos = tag.getPos();
1569          if (ignoreWhitespace)
1570          {
1571              tagPos = getMagicEndPos(tagPos);
1572          }
1573  
1574          // Output an end tag to close this start tag, then update the context
1575          var endTag = new Tag(Tag.END_TAG, openTagName, tagPos, 0);
1576          endTag.setFlags(openTag.getFlags());
1577          outputTag(endTag);
1578          popContext();
1579      });
1580  
1581      // Output our tag, moving the cursor past it, then update the context
1582      outputTag(tag);
1583      popContext();
1584  
1585      // If our fixing budget allows it, peek at upcoming tags and remove end tags that would
1586      // close tags that are already being closed now. Also, filter our list of tags being
1587      // reopened by removing those that would immediately be closed
1588      if (closeTags.length && currentFixingCost < maxFixingCost)
1589      {
1590          /**
1591          * @type {number} Rightmost position of the portion of text to ignore
1592          */
1593          var ignorePos = pos;
1594  
1595          i = tagStack.length;
1596          while (--i >= 0 && ++currentFixingCost < maxFixingCost)
1597          {
1598              var upcomingTag = tagStack[i];
1599  
1600              // Test whether the upcoming tag is positioned at current "ignore" position and it's
1601              // strictly an end tag (not a start tag or a self-closing tag)
1602              if (upcomingTag.getPos() > ignorePos
1603               || upcomingTag.isStartTag())
1604              {
1605                  break;
1606              }
1607  
1608              // Test whether this tag would close any of the tags we're about to reopen
1609              var j = closeTags.length;
1610  
1611              while (--j >= 0 && ++currentFixingCost < maxFixingCost)
1612              {
1613                  if (upcomingTag.canClose(closeTags[j]))
1614                  {
1615                      // Remove the tag from the lists and reset the keys
1616                      closeTags.splice(j, 1);
1617  
1618                      if (reopenTags[j])
1619                      {
1620                          reopenTags.splice(j, 1);
1621                      }
1622  
1623                      // Extend the ignored text to cover this tag
1624                      ignorePos = Math.max(
1625                          ignorePos,
1626                          upcomingTag.getPos() + upcomingTag.getLen()
1627                      );
1628  
1629                      break;
1630                  }
1631              }
1632          }
1633  
1634          if (ignorePos > pos)
1635          {
1636              /**
1637              * @todo have a method that takes (pos,len) rather than a Tag
1638              */
1639              outputIgnoreTag(new Tag(Tag.SELF_CLOSING_TAG, 'i', pos, ignorePos - pos));
1640          }
1641      }
1642  
1643      // Re-add tags that need to be reopened, at current cursor position
1644      reopenTags.forEach(function(startTag)
1645      {
1646          var newTag = addCopyTag(startTag, pos, 0);
1647  
1648          // Re-pair the new tag
1649          var endTag = startTag.getEndTag();
1650          if (endTag)
1651          {
1652              newTag.pairWith(endTag);
1653          }
1654      });
1655  }
1656  
1657  /**
1658  * Update counters and replace current context with its parent context
1659  */
1660  function popContext()
1661  {
1662      var tag = openTags.pop();
1663      --cntOpen[tag.getName()];
1664      context = context.parentContext;
1665  }
1666  
1667  /**
1668  * Update counters and replace current context with a new context based on given tag
1669  *
1670  * If given tag is a self-closing tag, the context won't change
1671  *
1672  * @param {!Tag} tag Start tag (including self-closing)
1673  */
1674  function pushContext(tag)
1675  {
1676      var tagName   = tag.getName(),
1677          tagFlags  = tag.getFlags(),
1678          tagConfig = tagsConfig[tagName];
1679  
1680      ++cntTotal[tagName];
1681  
1682      // If this is a self-closing tag, the context remains the same
1683      if (tag.isSelfClosingTag())
1684      {
1685          return;
1686      }
1687  
1688      // Recompute the allowed tags
1689      var allowed = [];
1690      if (HINT.RULE_IS_TRANSPARENT && (tagFlags & RULE_IS_TRANSPARENT))
1691      {
1692          context.allowed.forEach(function(v, k)
1693          {
1694              allowed.push(tagConfig.allowed[k] & v);
1695          });
1696      }
1697      else
1698      {
1699          context.allowed.forEach(function(v, k)
1700          {
1701              allowed.push(tagConfig.allowed[k] & ((v & 0xFF00) | (v >> 8)));
1702          });
1703      }
1704  
1705      // Use this tag's flags as a base for this context and add inherited rules
1706      var flags = tagFlags | (context.flags & RULES_INHERITANCE);
1707  
1708      // RULE_DISABLE_AUTO_BR turns off RULE_ENABLE_AUTO_BR
1709      if (flags & RULE_DISABLE_AUTO_BR)
1710      {
1711          flags &= ~RULE_ENABLE_AUTO_BR;
1712      }
1713  
1714      ++cntOpen[tagName];
1715      openTags.push(tag);
1716      context = {
1717          allowed       : allowed,
1718          flags         : flags,
1719          parentContext : context
1720      };
1721  }
1722  
1723  /**
1724  * Return whether given tag is allowed in current context
1725  *
1726  * @param  {!string}  tagName
1727  * @return {!boolean}
1728  */
1729  function tagIsAllowed(tagName)
1730  {
1731      var n = tagsConfig[tagName].bitNumber;
1732  
1733      return !!(context.allowed[n >> 3] & (1 << (n & 7)));
1734  }
1735  
1736  //==========================================================================
1737  // Tag stack
1738  //==========================================================================
1739  
1740  /**
1741  * Add a start tag
1742  *
1743  * @param  {!string} name Name of the tag
1744  * @param  {!number} pos  Position of the tag in the text
1745  * @param  {!number} len  Length of text consumed by the tag
1746  * @param  {number=} prio Tags' priority
1747  * @return {!Tag}
1748  */
1749  function addStartTag(name, pos, len, prio)
1750  {
1751      return addTag(Tag.START_TAG, name, pos, len, prio || 0);
1752  }
1753  
1754  /**
1755  * Add an end tag
1756  *
1757  * @param  {!string} name Name of the tag
1758  * @param  {!number} pos  Position of the tag in the text
1759  * @param  {!number} len  Length of text consumed by the tag
1760  * @param  {number=} prio Tags' priority
1761  * @return {!Tag}
1762  */
1763  function addEndTag(name, pos, len, prio)
1764  {
1765      return addTag(Tag.END_TAG, name, pos, len, prio || 0);
1766  }
1767  
1768  /**
1769  * Add a self-closing tag
1770  *
1771  * @param  {!string} name Name of the tag
1772  * @param  {!number} pos  Position of the tag in the text
1773  * @param  {!number} len  Length of text consumed by the tag
1774  * @param  {number=} prio Tags' priority
1775  * @return {!Tag}
1776  */
1777  function addSelfClosingTag(name, pos, len, prio)
1778  {
1779      return addTag(Tag.SELF_CLOSING_TAG, name, pos, len, prio || 0);
1780  }
1781  
1782  /**
1783  * Add a 0-width "br" tag to force a line break at given position
1784  *
1785  * @param  {!number} pos  Position of the tag in the text
1786  * @param  {number=} prio Tags' priority
1787  * @return {!Tag}
1788  */
1789  function addBrTag(pos, prio)
1790  {
1791      return addTag(Tag.SELF_CLOSING_TAG, 'br', pos, 0, prio || 0);
1792  }
1793  
1794  /**
1795  * Add an "ignore" tag
1796  *
1797  * @param  {!number} pos  Position of the tag in the text
1798  * @param  {!number} len  Length of text consumed by the tag
1799  * @param  {number=} prio Tags' priority
1800  * @return {!Tag}
1801  */
1802  function addIgnoreTag(pos, len, prio)
1803  {
1804      return addTag(Tag.SELF_CLOSING_TAG, 'i', pos, Math.min(len, textLen - pos), prio || 0);
1805  }
1806  
1807  /**
1808  * Add a paragraph break at given position
1809  *
1810  * Uses a zero-width tag that is actually never output in the result
1811  *
1812  * @param  {!number} pos  Position of the tag in the text
1813  * @param  {number=} prio Tags' priority
1814  * @return {!Tag}
1815  */
1816  function addParagraphBreak(pos, prio)
1817  {
1818      return addTag(Tag.SELF_CLOSING_TAG, 'pb', pos, 0, prio || 0);
1819  }
1820  
1821  /**
1822  * Add a copy of given tag at given position and length
1823  *
1824  * @param  {!Tag}    tag Original tag
1825  * @param  {!number} pos Copy's position
1826  * @param  {!number} len Copy's length
1827  * @param  {number=} prio Tags' priority
1828  * @return {!Tag}         Copy tag
1829  */
1830  function addCopyTag(tag, pos, len, prio)
1831  {
1832      var copy = addTag(tag.getType(), tag.getName(), pos, len, tag.getSortPriority());
1833      copy.setAttributes(tag.getAttributes());
1834  
1835      return copy;
1836  }
1837  
1838  /**
1839  * Add a tag
1840  *
1841  * @param  {!number} type Tag's type
1842  * @param  {!string} name Name of the tag
1843  * @param  {!number} pos  Position of the tag in the text
1844  * @param  {!number} len  Length of text consumed by the tag
1845  * @param  {number=} prio Tags' priority
1846  * @return {!Tag}
1847  */
1848  function addTag(type, name, pos, len, prio)
1849  {
1850      // Create the tag
1851      var tag = new Tag(type, name, pos, len, prio || 0);
1852  
1853      // Set this tag's rules bitfield
1854      if (tagsConfig[name])
1855      {
1856          tag.setFlags(tagsConfig[name].rules.flags);
1857      }
1858  
1859      // Invalidate this tag if it's an unknown tag, a disabled tag, if either of its length or
1860      // position is negative or if it's out of bounds
1861      if ((!tagsConfig[name] && !tag.isSystemTag()) || isInvalidTextSpan(pos, len))
1862      {
1863          tag.invalidate();
1864      }
1865      else if (tagsConfig[name] && tagsConfig[name].isDisabled)
1866      {
1867          logger.warn(
1868              'Tag is disabled',
1869              {
1870                  'tag'     : tag,
1871                  'tagName' : name
1872              }
1873          );
1874          tag.invalidate();
1875      }
1876      else
1877      {
1878          insertTag(tag);
1879      }
1880  
1881      return tag;
1882  }
1883  
1884  /**
1885  * Test whether given text span is outside text boundaries or an invalid UTF sequence
1886  *
1887  * @param  {number}  pos Start of text
1888  * @param  {number}  len Length of text
1889  * @return {boolean}
1890  */
1891  function isInvalidTextSpan(pos, len)
1892  {
1893      return (len < 0 || pos < 0 || pos + len > textLen || /[\uDC00-\uDFFF]/.test(text.substr(pos, 1) + text.substr(pos + len, 1)));
1894  }
1895  
1896  /**
1897  * Insert given tag in the tag stack
1898  *
1899  * @param {!Tag} tag
1900  */
1901  function insertTag(tag)
1902  {
1903      if (!tagStackIsSorted)
1904      {
1905          tagStack.push(tag);
1906      }
1907      else
1908      {
1909          // Scan the stack and copy every tag to the next slot until we find the correct index
1910          var i = tagStack.length;
1911          while (i > 0 && compareTags(tagStack[i - 1], tag) > 0)
1912          {
1913              tagStack[i] = tagStack[i - 1];
1914              --i;
1915          }
1916          tagStack[i] = tag;
1917      }
1918  }
1919  
1920  /**
1921  * Add a pair of tags
1922  *
1923  * @param  {!string} name     Name of the tags
1924  * @param  {!number} startPos Position of the start tag
1925  * @param  {!number} startLen Length of the start tag
1926  * @param  {!number} endPos   Position of the start tag
1927  * @param  {!number} endLen   Length of the start tag
1928  * @param  {number=}  prio     Start tag's priority (the end tag will be set to minus that value)
1929  * @return {!Tag}             Start tag
1930  */
1931  function addTagPair(name, startPos, startLen, endPos, endLen, prio)
1932  {
1933      // NOTE: the end tag is added first to try to keep the stack in the correct order
1934      var endTag   = addEndTag(name, endPos, endLen, -prio || 0),
1935          startTag = addStartTag(name, startPos, startLen, prio || 0);
1936      startTag.pairWith(endTag);
1937  
1938      return startTag;
1939  }
1940  
1941  /**
1942  * Add a tag that represents a verbatim copy of the original text
1943  *
1944  * @param  {!number} pos  Position of the tag in the text
1945  * @param  {!number} len  Length of text consumed by the tag
1946  * @return {!Tag}
1947  */
1948  function addVerbatim(pos, len, prio)
1949  {
1950      return addTag(Tag.SELF_CLOSING_TAG, 'v', pos, len, prio || 0);
1951  }
1952  
1953  /**
1954  * Sort tags by position and precedence
1955  */
1956  function sortTags()
1957  {
1958      tagStack.sort(compareTags);
1959      tagStackIsSorted = true;
1960  }
1961  
1962  /**
1963  * sortTags() callback
1964  *
1965  * Tags are stored as a stack, in LIFO order. We sort tags by position _descending_ so that they
1966  * are processed in the order they appear in the text.
1967  *
1968  * @param  {!Tag}    a First tag to compare
1969  * @param  {!Tag}    b Second tag to compare
1970  * @return {!number}
1971  */
1972  function compareTags(a, b)
1973  {
1974      var aPos = a.getPos(),
1975          bPos = b.getPos();
1976  
1977      // First we order by pos descending
1978      if (aPos !== bPos)
1979      {
1980          return bPos - aPos;
1981      }
1982  
1983      // If the tags start at the same position, we'll use their sortPriority if applicable. Tags
1984      // with a lower value get sorted last, which means they'll be processed first. IOW, -10 is
1985      // processed before 10
1986      if (a.getSortPriority() !== b.getSortPriority())
1987      {
1988          return b.getSortPriority() - a.getSortPriority();
1989      }
1990  
1991      // If the tags start at the same position and have the same priority, we'll sort them
1992      // according to their length, with special considerations for  zero-width tags
1993      var aLen = a.getLen(),
1994          bLen = b.getLen();
1995  
1996      if (!aLen || !bLen)
1997      {
1998          // Zero-width end tags are ordered after zero-width start tags so that a pair that ends
1999          // with a zero-width tag has the opportunity to be closed before another pair starts
2000          // with a zero-width tag. For example, the pairs that would enclose each of the letters
2001          // in the string "XY". Self-closing tags are ordered between end tags and start tags in
2002          // an attempt to keep them out of tag pairs
2003          if (!aLen && !bLen)
2004          {
2005              var order = {};
2006              order[Tag.END_TAG]          = 0;
2007              order[Tag.SELF_CLOSING_TAG] = 1;
2008              order[Tag.START_TAG]        = 2;
2009  
2010              return order[b.getType()] - order[a.getType()];
2011          }
2012  
2013          // Here, we know that only one of a or b is a zero-width tags. Zero-width tags are
2014          // ordered after wider tags so that they have a chance to be processed before the next
2015          // character is consumed, which would force them to be skipped
2016          return (aLen) ? -1 : 1;
2017      }
2018  
2019      // Here we know that both tags start at the same position and have a length greater than 0.
2020      // We sort tags by length ascending, so that the longest matches are processed first. If
2021      // their length is identical, the order is undefined as PHP's sort isn't stable
2022      return aLen - bLen;
2023  }