aboutsummaryrefslogtreecommitdiff
path: root/js/lib/blocks.js
blob: 617d60d7fe651786c746454da5835c687dd0b1a9 (plain)
  1. "use strict";
  2. var Node = require('./node');
  3. var unescapeString = require('./common').unescapeString;
  4. var C_GREATERTHAN = 62;
  5. var C_NEWLINE = 10;
  6. var C_SPACE = 32;
  7. var C_OPEN_BRACKET = 91;
  8. var InlineParser = require('./inlines');
  9. var BLOCKTAGNAME = '(?:article|header|aside|hgroup|iframe|blockquote|hr|body|li|map|button|object|canvas|ol|caption|output|col|p|colgroup|pre|dd|progress|div|section|dl|table|td|dt|tbody|embed|textarea|fieldset|tfoot|figcaption|th|figure|thead|footer|footer|tr|form|ul|h1|h2|h3|h4|h5|h6|video|script|style)';
  10. var HTMLBLOCKOPEN = "<(?:" + BLOCKTAGNAME + "[\\s/>]" + "|" +
  11. "/" + BLOCKTAGNAME + "[\\s>]" + "|" + "[?!])";
  12. var reHtmlBlockOpen = new RegExp('^' + HTMLBLOCKOPEN, 'i');
  13. var reHrule = /^(?:(?:\* *){3,}|(?:_ *){3,}|(?:- *){3,}) *$/;
  14. var reMaybeSpecial = /^[ #`~*+_=<>0-9-]/;
  15. var reNonSpace = /[^ \t\n]/;
  16. var reBulletListMarker = /^[*+-]( +|$)/;
  17. var reOrderedListMarker = /^(\d+)([.)])( +|$)/;
  18. var reATXHeaderMarker = /^#{1,6}(?: +|$)/;
  19. var reCodeFence = /^`{3,}(?!.*`)|^~{3,}(?!.*~)/;
  20. var reClosingCodeFence = /^(?:`{3,}|~{3,})(?= *$)/;
  21. var reSetextHeaderLine = /^(?:=+|-+) *$/;
  22. var reLineEnding = /\r\n|\n|\r/;
  23. // Returns true if string contains only space characters.
  24. var isBlank = function(s) {
  25. return !(reNonSpace.test(s));
  26. };
  27. var tabSpaces = [' ', ' ', ' ', ' '];
  28. // Convert tabs to spaces on each line using a 4-space tab stop.
  29. var detabLine = function(text) {
  30. var start = 0;
  31. var offset;
  32. var lastStop = 0;
  33. while ((offset = text.indexOf('\t', start)) !== -1) {
  34. var numspaces = (offset - lastStop) % 4;
  35. var spaces = tabSpaces[numspaces];
  36. text = text.slice(0, offset) + spaces + text.slice(offset + 1);
  37. lastStop = offset + numspaces;
  38. start = lastStop;
  39. }
  40. return text;
  41. };
  42. // Attempt to match a regex in string s at offset offset.
  43. // Return index of match or -1.
  44. var matchAt = function(re, s, offset) {
  45. var res = s.slice(offset).match(re);
  46. if (res === null) {
  47. return -1;
  48. } else {
  49. return offset + res.index;
  50. }
  51. };
  52. // destructively trip final blank lines in an array of strings
  53. var stripFinalBlankLines = function(lns) {
  54. var i = lns.length - 1;
  55. while (!reNonSpace.test(lns[i])) {
  56. lns.pop();
  57. i--;
  58. }
  59. };
  60. // DOC PARSER
  61. // These are methods of a DocParser object, defined below.
  62. // Returns true if parent block can contain child block.
  63. var canContain = function(parent_type, child_type) {
  64. return ( parent_type === 'Document' ||
  65. parent_type === 'BlockQuote' ||
  66. parent_type === 'Item' ||
  67. (parent_type === 'List' && child_type === 'Item') );
  68. };
  69. // Returns true if block type can accept lines of text.
  70. var acceptsLines = function(block_type) {
  71. return ( block_type === 'Paragraph' ||
  72. block_type === 'CodeBlock' );
  73. };
  74. // Returns true if block ends with a blank line, descending if needed
  75. // into lists and sublists.
  76. var endsWithBlankLine = function(block) {
  77. while (block) {
  78. if (block.last_line_blank) {
  79. return true;
  80. }
  81. var t = block.getType();
  82. if (t === 'List' || t === 'Item') {
  83. block = block.lastChild;
  84. } else {
  85. break;
  86. }
  87. }
  88. return false;
  89. };
  90. // Break out of all containing lists, resetting the tip of the
  91. // document to the parent of the highest list, and finalizing
  92. // all the lists. (This is used to implement the "two blank lines
  93. // break of of all lists" feature.)
  94. var breakOutOfLists = function(block) {
  95. var b = block;
  96. var last_list = null;
  97. do {
  98. if (b.getType() === 'List') {
  99. last_list = b;
  100. }
  101. b = b.parent;
  102. } while (b);
  103. if (last_list) {
  104. while (block !== last_list) {
  105. this.finalize(block, this.lineNumber);
  106. block = block.parent;
  107. }
  108. this.finalize(last_list, this.lineNumber);
  109. this.tip = last_list.parent;
  110. }
  111. };
  112. // Add a line to the block at the tip. We assume the tip
  113. // can accept lines -- that check should be done before calling this.
  114. var addLine = function(ln, offset) {
  115. var s = ln.slice(offset);
  116. if (!(this.tip.open)) {
  117. throw { msg: "Attempted to add line (" + ln + ") to closed container." };
  118. }
  119. this.tip.strings.push(s);
  120. };
  121. // Add block of type tag as a child of the tip. If the tip can't
  122. // accept children, close and finalize it and try its parent,
  123. // and so on til we find a block that can accept children.
  124. var addChild = function(tag, offset) {
  125. while (!canContain(this.tip.getType(), tag)) {
  126. this.finalize(this.tip, this.lineNumber - 1);
  127. }
  128. var column_number = offset + 1; // offset 0 = column 1
  129. var newBlock = new Node(tag, [[this.lineNumber, column_number], [0, 0]]);
  130. newBlock.strings = [];
  131. newBlock.string_content = null;
  132. this.tip.appendChild(newBlock);
  133. this.tip = newBlock;
  134. return newBlock;
  135. };
  136. // Parse a list marker and return data on the marker (type,
  137. // start, delimiter, bullet character, padding) or null.
  138. var parseListMarker = function(ln, offset, indent) {
  139. var rest = ln.slice(offset);
  140. var match;
  141. var spaces_after_marker;
  142. var data = { type: null,
  143. tight: true,
  144. bullet_char: null,
  145. start: null,
  146. delimiter: null,
  147. padding: null,
  148. marker_offset: indent };
  149. if (rest.match(reHrule)) {
  150. return null;
  151. }
  152. if ((match = rest.match(reBulletListMarker))) {
  153. spaces_after_marker = match[1].length;
  154. data.type = 'Bullet';
  155. data.bullet_char = match[0][0];
  156. } else if ((match = rest.match(reOrderedListMarker))) {
  157. spaces_after_marker = match[3].length;
  158. data.type = 'Ordered';
  159. data.start = parseInt(match[1]);
  160. data.delimiter = match[2];
  161. } else {
  162. return null;
  163. }
  164. var blank_item = match[0].length === rest.length;
  165. if (spaces_after_marker >= 5 ||
  166. spaces_after_marker < 1 ||
  167. blank_item) {
  168. data.padding = match[0].length - spaces_after_marker + 1;
  169. } else {
  170. data.padding = match[0].length;
  171. }
  172. return data;
  173. };
  174. // Returns true if the two list items are of the same type,
  175. // with the same delimiter and bullet character. This is used
  176. // in agglomerating list items into lists.
  177. var listsMatch = function(list_data, item_data) {
  178. return (list_data.type === item_data.type &&
  179. list_data.delimiter === item_data.delimiter &&
  180. list_data.bullet_char === item_data.bullet_char);
  181. };
  182. // Finalize and close any unmatched blocks. Returns true.
  183. var closeUnmatchedBlocks = function() {
  184. // finalize any blocks not matched
  185. while (this.oldtip !== this.lastMatchedContainer) {
  186. this.finalize(this.oldtip, this.lineNumber - 1);
  187. this.oldtip = this.oldtip.parent;
  188. }
  189. return true;
  190. };
  191. // Analyze a line of text and update the document appropriately.
  192. // We parse markdown text by calling this on each line of input,
  193. // then finalizing the document.
  194. var incorporateLine = function(ln) {
  195. var all_matched = true;
  196. var first_nonspace;
  197. var offset = 0;
  198. var match;
  199. var data;
  200. var blank;
  201. var indent;
  202. var i;
  203. var CODE_INDENT = 4;
  204. var allClosed;
  205. var container = this.doc;
  206. this.oldtip = this.tip;
  207. // replace NUL characters for security
  208. if (ln.indexOf('\u0000') !== -1) {
  209. ln = ln.replace(/\0/g, '\uFFFD');
  210. }
  211. // Convert tabs to spaces:
  212. ln = detabLine(ln);
  213. // For each containing block, try to parse the associated line start.
  214. // Bail out on failure: container will point to the last matching block.
  215. // Set all_matched to false if not all containers match.
  216. while (container.lastChild) {
  217. if (!container.lastChild.open) {
  218. break;
  219. }
  220. container = container.lastChild;
  221. match = matchAt(reNonSpace, ln, offset);
  222. if (match === -1) {
  223. first_nonspace = ln.length;
  224. blank = true;
  225. } else {
  226. first_nonspace = match;
  227. blank = false;
  228. }
  229. indent = first_nonspace - offset;
  230. switch (container.getType()) {
  231. case 'BlockQuote':
  232. if (indent <= 3 && ln.charCodeAt(first_nonspace) === C_GREATERTHAN) {
  233. offset = first_nonspace + 1;
  234. if (ln.charCodeAt(offset) === C_SPACE) {
  235. offset++;
  236. }
  237. } else {
  238. all_matched = false;
  239. }
  240. break;
  241. case 'Item':
  242. if (indent >= container.list_data.marker_offset +
  243. container.list_data.padding) {
  244. offset += container.list_data.marker_offset +
  245. container.list_data.padding;
  246. } else if (blank) {
  247. offset = first_nonspace;
  248. } else {
  249. all_matched = false;
  250. }
  251. break;
  252. case 'Header':
  253. case 'HorizontalRule':
  254. // a header can never container > 1 line, so fail to match:
  255. all_matched = false;
  256. if (blank) {
  257. container.last_line_blank = true;
  258. }
  259. break;
  260. case 'CodeBlock':
  261. if (container.fence_length > 0) { // fenced
  262. // skip optional spaces of fence offset
  263. i = container.fence_offset;
  264. while (i > 0 && ln.charCodeAt(offset) === C_SPACE) {
  265. offset++;
  266. i--;
  267. }
  268. } else { // indented
  269. if (indent >= CODE_INDENT) {
  270. offset += CODE_INDENT;
  271. } else if (blank) {
  272. offset = first_nonspace;
  273. } else {
  274. all_matched = false;
  275. }
  276. }
  277. break;
  278. case 'HtmlBlock':
  279. if (blank) {
  280. container.last_line_blank = true;
  281. all_matched = false;
  282. }
  283. break;
  284. case 'Paragraph':
  285. if (blank) {
  286. container.last_line_blank = true;
  287. all_matched = false;
  288. }
  289. break;
  290. default:
  291. }
  292. if (!all_matched) {
  293. container = container.parent; // back up to last matching block
  294. break;
  295. }
  296. }
  297. allClosed = (container === this.oldtip);
  298. this.lastMatchedContainer = container;
  299. // Check to see if we've hit 2nd blank line; if so break out of list:
  300. if (blank && container.last_line_blank) {
  301. this.breakOutOfLists(container);
  302. }
  303. // Unless last matched container is a code block, try new container starts,
  304. // adding children to the last matched container:
  305. var t = container.getType();
  306. while (t !== 'CodeBlock' && t !== 'HtmlBlock' &&
  307. // this is a little performance optimization:
  308. matchAt(reMaybeSpecial, ln, offset) !== -1) {
  309. match = matchAt(reNonSpace, ln, offset);
  310. if (match === -1) {
  311. first_nonspace = ln.length;
  312. blank = true;
  313. break;
  314. } else {
  315. first_nonspace = match;
  316. blank = false;
  317. }
  318. indent = first_nonspace - offset;
  319. if (indent >= CODE_INDENT) {
  320. // indented code
  321. if (this.tip.getType() !== 'Paragraph' && !blank) {
  322. offset += CODE_INDENT;
  323. allClosed = allClosed ||
  324. this.closeUnmatchedBlocks();
  325. container = this.addChild('CodeBlock', offset);
  326. }
  327. break;
  328. }
  329. offset = first_nonspace;
  330. var cc = ln.charCodeAt(offset);
  331. if (cc === C_GREATERTHAN) {
  332. // blockquote
  333. offset += 1;
  334. // optional following space
  335. if (ln.charCodeAt(offset) === C_SPACE) {
  336. offset++;
  337. }
  338. allClosed = allClosed || this.closeUnmatchedBlocks();
  339. container = this.addChild('BlockQuote', first_nonspace);
  340. } else if ((match = ln.slice(offset).match(reATXHeaderMarker))) {
  341. // ATX header
  342. offset += match[0].length;
  343. allClosed = allClosed || this.closeUnmatchedBlocks();
  344. container = this.addChild('Header', first_nonspace);
  345. container.level = match[0].trim().length; // number of #s
  346. // remove trailing ###s:
  347. container.strings =
  348. [ln.slice(offset).replace(/^ *#+ *$/, '').replace(/ +#+ *$/, '')];
  349. break;
  350. } else if ((match = ln.slice(offset).match(reCodeFence))) {
  351. // fenced code block
  352. var fence_length = match[0].length;
  353. allClosed = allClosed || this.closeUnmatchedBlocks();
  354. container = this.addChild('CodeBlock', first_nonspace);
  355. container.fence_length = fence_length;
  356. container.fence_char = match[0][0];
  357. container.fence_offset = indent;
  358. offset += fence_length;
  359. break;
  360. } else if (matchAt(reHtmlBlockOpen, ln, offset) !== -1) {
  361. // html block
  362. allClosed = allClosed || this.closeUnmatchedBlocks();
  363. container = this.addChild('HtmlBlock', offset);
  364. offset -= indent; // back up so spaces are part of block
  365. break;
  366. } else if (container.getType() === 'Paragraph' &&
  367. container.strings.length === 1 &&
  368. ((match = ln.slice(offset).match(reSetextHeaderLine)))) {
  369. // setext header line
  370. allClosed = allClosed || this.closeUnmatchedBlocks();
  371. container.setType('Header'); // convert Paragraph to SetextHeader
  372. container.level = match[0][0] === '=' ? 1 : 2;
  373. offset = ln.length;
  374. break;
  375. } else if (matchAt(reHrule, ln, offset) !== -1) {
  376. // hrule
  377. allClosed = allClosed || this.closeUnmatchedBlocks();
  378. container = this.addChild('HorizontalRule', first_nonspace);
  379. offset = ln.length - 1;
  380. break;
  381. } else if ((data = parseListMarker(ln, offset, indent))) {
  382. // list item
  383. allClosed = allClosed || this.closeUnmatchedBlocks();
  384. offset += data.padding;
  385. // add the list if needed
  386. if (container.getType() !== 'List' ||
  387. !(listsMatch(container.list_data, data))) {
  388. container = this.addChild('List', first_nonspace);
  389. container.list_data = data;
  390. }
  391. // add the list item
  392. container = this.addChild('Item', first_nonspace);
  393. container.list_data = data;
  394. } else {
  395. break;
  396. }
  397. }
  398. // What remains at the offset is a text line. Add the text to the
  399. // appropriate container.
  400. match = matchAt(reNonSpace, ln, offset);
  401. if (match === -1) {
  402. first_nonspace = ln.length;
  403. blank = true;
  404. } else {
  405. first_nonspace = match;
  406. blank = false;
  407. }
  408. indent = first_nonspace - offset;
  409. // First check for a lazy paragraph continuation:
  410. if (!allClosed && !blank &&
  411. this.tip.getType() === 'Paragraph' &&
  412. this.tip.strings.length > 0) {
  413. // lazy paragraph continuation
  414. this.last_line_blank = false;
  415. this.addLine(ln, offset);
  416. } else { // not a lazy continuation
  417. // finalize any blocks not matched
  418. allClosed = allClosed || this.closeUnmatchedBlocks();
  419. // Block quote lines are never blank as they start with >
  420. // and we don't count blanks in fenced code for purposes of tight/loose
  421. // lists or breaking out of lists. We also don't set last_line_blank
  422. // on an empty list item.
  423. var t = container.getType();
  424. container.last_line_blank = blank &&
  425. !(t === 'BlockQuote' ||
  426. t === 'Header' ||
  427. (t === 'CodeBlock' && container.fence_length > 0) ||
  428. (t === 'Item' &&
  429. !container.firstChild &&
  430. container.sourcepos[0][0] === this.lineNumber));
  431. var cont = container;
  432. while (cont.parent) {
  433. cont.parent.last_line_blank = false;
  434. cont = cont.parent;
  435. }
  436. switch (container.getType()) {
  437. case 'HtmlBlock':
  438. this.addLine(ln, offset);
  439. break;
  440. case 'CodeBlock':
  441. if (container.fence_length > 0) { // fenced
  442. // check for closing code fence:
  443. match = (indent <= 3 &&
  444. ln.charAt(first_nonspace) === container.fence_char &&
  445. ln.slice(first_nonspace).match(reClosingCodeFence));
  446. if (match && match[0].length >= container.fence_length) {
  447. // don't add closing fence to container; instead, close it:
  448. this.finalize(container, this.lineNumber);
  449. } else {
  450. this.addLine(ln, offset);
  451. }
  452. } else { // indented
  453. this.addLine(ln, offset);
  454. }
  455. break;
  456. case 'Header':
  457. case 'HorizontalRule':
  458. // nothing to do; we already added the contents.
  459. break;
  460. default:
  461. if (acceptsLines(container.getType())) {
  462. this.addLine(ln, first_nonspace);
  463. } else if (blank) {
  464. break;
  465. } else {
  466. // create paragraph container for line
  467. container = this.addChild('Paragraph', this.lineNumber, first_nonspace);
  468. this.addLine(ln, first_nonspace);
  469. }
  470. }
  471. }
  472. this.lastLineLength = ln.length - 1; // -1 for newline
  473. };
  474. // Finalize a block. Close it and do any necessary postprocessing,
  475. // e.g. creating string_content from strings, setting the 'tight'
  476. // or 'loose' status of a list, and parsing the beginnings
  477. // of paragraphs for reference definitions. Reset the tip to the
  478. // parent of the closed block.
  479. var finalize = function(block, lineNumber) {
  480. var pos;
  481. // don't do anything if the block is already closed
  482. if (!block.open) {
  483. return 0;
  484. }
  485. block.open = false;
  486. block.sourcepos[1] = [lineNumber, this.lastLineLength + 1];
  487. switch (block.getType()) {
  488. case 'Paragraph':
  489. block.string_content = block.strings.join('\n');
  490. // try parsing the beginning as link reference definitions:
  491. while (block.string_content.charCodeAt(0) === C_OPEN_BRACKET &&
  492. (pos = this.inlineParser.parseReference(block.string_content,
  493. this.refmap))) {
  494. block.string_content = block.string_content.slice(pos);
  495. if (isBlank(block.string_content)) {
  496. block.setType('ReferenceDef');
  497. break;
  498. }
  499. }
  500. break;
  501. case 'Header':
  502. block.string_content = block.strings.join('\n');
  503. break;
  504. case 'HtmlBlock':
  505. block.literal = block.strings.join('\n');
  506. break;
  507. case 'CodeBlock':
  508. if (block.fence_length > 0) { // fenced
  509. // first line becomes info string
  510. block.info = unescapeString(block.strings[0].trim());
  511. if (block.strings.length === 1) {
  512. block.literal = '';
  513. } else {
  514. block.literal = block.strings.slice(1).join('\n') + '\n';
  515. }
  516. } else { // indented
  517. stripFinalBlankLines(block.strings);
  518. block.literal = block.strings.join('\n') + '\n';
  519. }
  520. break;
  521. case 'List':
  522. block.list_data.tight = true; // tight by default
  523. var item = block.firstChild;
  524. while (item) {
  525. // check for non-final list item ending with blank line:
  526. if (endsWithBlankLine(item) && item.next) {
  527. block.list_data.tight = false;
  528. break;
  529. }
  530. // recurse into children of list item, to see if there are
  531. // spaces between any of them:
  532. var subitem = item.firstChild;
  533. while (subitem) {
  534. if (endsWithBlankLine(subitem) && (item.next || subitem.next)) {
  535. block.list_data.tight = false;
  536. break;
  537. }
  538. subitem = subitem.next;
  539. }
  540. item = item.next;
  541. }
  542. break;
  543. default:
  544. break;
  545. }
  546. this.tip = block.parent || this.top;
  547. };
  548. // Walk through a block & children recursively, parsing string content
  549. // into inline content where appropriate. Returns new object.
  550. var processInlines = function(block) {
  551. var node, event, t;
  552. var walker = block.walker();
  553. while ((event = walker.next())) {
  554. node = event.node;
  555. t = node.getType();
  556. if (!event.entering && (t === 'Paragraph' || t === 'Header')) {
  557. this.inlineParser.parse(node, this.refmap);
  558. }
  559. }
  560. };
  561. var Document = function() {
  562. var doc = new Node('Document', [[1, 1], [0, 0]]);
  563. doc.string_content = null;
  564. doc.strings = [];
  565. return doc;
  566. };
  567. // The main parsing function. Returns a parsed document AST.
  568. var parse = function(input) {
  569. this.doc = new Document();
  570. this.tip = this.doc;
  571. this.refmap = {};
  572. if (this.options.time) { console.time("preparing input"); }
  573. var lines = input.split(reLineEnding);
  574. var len = lines.length;
  575. if (input.charCodeAt(input.length - 1) === C_NEWLINE) {
  576. // ignore last blank line created by final newline
  577. len -= 1;
  578. }
  579. if (this.options.time) { console.timeEnd("preparing input"); }
  580. if (this.options.time) { console.time("block parsing"); }
  581. for (var i = 0; i < len; i++) {
  582. this.lineNumber += 1;
  583. this.incorporateLine(lines[i]);
  584. }
  585. while (this.tip) {
  586. this.finalize(this.tip, len);
  587. }
  588. if (this.options.time) { console.timeEnd("block parsing"); }
  589. if (this.options.time) { console.time("inline parsing"); }
  590. this.processInlines(this.doc);
  591. if (this.options.time) { console.timeEnd("inline parsing"); }
  592. return this.doc;
  593. };
  594. // The DocParser object.
  595. function DocParser(options){
  596. return {
  597. doc: new Document(),
  598. tip: this.doc,
  599. oldtip: this.doc,
  600. lineNumber: 0,
  601. lastMatchedContainer: this.doc,
  602. refmap: {},
  603. lastLineLength: 0,
  604. inlineParser: new InlineParser(),
  605. breakOutOfLists: breakOutOfLists,
  606. addLine: addLine,
  607. addChild: addChild,
  608. incorporateLine: incorporateLine,
  609. finalize: finalize,
  610. processInlines: processInlines,
  611. closeUnmatchedBlocks: closeUnmatchedBlocks,
  612. parse: parse,
  613. options: options || {}
  614. };
  615. }
  616. module.exports = DocParser;