aboutsummaryrefslogtreecommitdiff
path: root/js/lib/blocks.js
blob: 5b013580676cbc58ebdd8ab9bffe16820fe2bef8 (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) {
  47. return offset + res.index;
  48. } else {
  49. return -1;
  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 === 'IndentedCode' ||
  73. block_type === 'FencedCode' );
  74. };
  75. // Returns true if block ends with a blank line, descending if needed
  76. // into lists and sublists.
  77. var endsWithBlankLine = function(block) {
  78. while (block) {
  79. if (block.last_line_blank) {
  80. return true;
  81. }
  82. if (block.t === 'List' || block.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, line_number) {
  95. var b = block;
  96. var last_list = null;
  97. do {
  98. if (b.t === '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, line_number);
  106. block = block.parent;
  107. }
  108. this.finalize(last_list, line_number);
  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, line_number, offset) {
  125. while (!canContain(this.tip.t, tag)) {
  126. this.finalize(this.tip, line_number - 1);
  127. }
  128. var column_number = offset + 1; // offset 0 = column 1
  129. var newBlock = new Node(tag, [[line_number, column_number], [0, 0]]);
  130. newBlock.strings = [];
  131. newBlock.string_content = undefined;
  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) {
  139. var rest = ln.slice(offset);
  140. var match;
  141. var spaces_after_marker;
  142. var data = { type: undefined,
  143. tight: true,
  144. bullet_char: undefined,
  145. start: undefined,
  146. delimiter: undefined,
  147. padding: undefined };
  148. if (rest.match(reHrule)) {
  149. return null;
  150. }
  151. if ((match = rest.match(reBulletListMarker))) {
  152. spaces_after_marker = match[1].length;
  153. data.type = 'Bullet';
  154. data.bullet_char = match[0][0];
  155. } else if ((match = rest.match(reOrderedListMarker))) {
  156. spaces_after_marker = match[3].length;
  157. data.type = 'Ordered';
  158. data.start = parseInt(match[1]);
  159. data.delimiter = match[2];
  160. } else {
  161. return null;
  162. }
  163. var blank_item = match[0].length === rest.length;
  164. if (spaces_after_marker >= 5 ||
  165. spaces_after_marker < 1 ||
  166. blank_item) {
  167. data.padding = match[0].length - spaces_after_marker + 1;
  168. } else {
  169. data.padding = match[0].length;
  170. }
  171. return data;
  172. };
  173. // Returns true if the two list items are of the same type,
  174. // with the same delimiter and bullet character. This is used
  175. // in agglomerating list items into lists.
  176. var listsMatch = function(list_data, item_data) {
  177. return (list_data.type === item_data.type &&
  178. list_data.delimiter === item_data.delimiter &&
  179. list_data.bullet_char === item_data.bullet_char);
  180. };
  181. // Analyze a line of text and update the document appropriately.
  182. // We parse markdown text by calling this on each line of input,
  183. // then finalizing the document.
  184. var incorporateLine = function(ln, line_number) {
  185. var all_matched = true;
  186. var first_nonspace;
  187. var offset = 0;
  188. var match;
  189. var data;
  190. var blank;
  191. var indent;
  192. var last_matched_container;
  193. var i;
  194. var CODE_INDENT = 4;
  195. var container = this.doc;
  196. var oldtip = this.tip;
  197. // replace NUL characters for security
  198. if (ln.indexOf('\u0000') !== -1) {
  199. ln = ln.replace(/\0/g, '\uFFFD');
  200. }
  201. // Convert tabs to spaces:
  202. ln = detabLine(ln);
  203. // For each containing block, try to parse the associated line start.
  204. // Bail out on failure: container will point to the last matching block.
  205. // Set all_matched to false if not all containers match.
  206. while (container.lastChild) {
  207. if (!container.lastChild.open) {
  208. break;
  209. }
  210. container = container.lastChild;
  211. match = matchAt(reNonSpace, ln, offset);
  212. if (match === -1) {
  213. first_nonspace = ln.length;
  214. blank = true;
  215. } else {
  216. first_nonspace = match;
  217. blank = false;
  218. }
  219. indent = first_nonspace - offset;
  220. switch (container.t) {
  221. case 'BlockQuote':
  222. if (indent <= 3 && ln.charCodeAt(first_nonspace) === C_GREATERTHAN) {
  223. offset = first_nonspace + 1;
  224. if (ln.charCodeAt(offset) === C_SPACE) {
  225. offset++;
  226. }
  227. } else {
  228. all_matched = false;
  229. }
  230. break;
  231. case 'Item':
  232. if (indent >= container.list_data.marker_offset +
  233. container.list_data.padding) {
  234. offset += container.list_data.marker_offset +
  235. container.list_data.padding;
  236. } else if (blank) {
  237. offset = first_nonspace;
  238. } else {
  239. all_matched = false;
  240. }
  241. break;
  242. case 'IndentedCode':
  243. if (indent >= CODE_INDENT) {
  244. offset += CODE_INDENT;
  245. } else if (blank) {
  246. offset = first_nonspace;
  247. } else {
  248. all_matched = false;
  249. }
  250. break;
  251. case 'Header':
  252. case 'HorizontalRule':
  253. // a header can never container > 1 line, so fail to match:
  254. all_matched = false;
  255. if (blank) {
  256. container.last_line_blank = true;
  257. }
  258. break;
  259. case 'FencedCode':
  260. // skip optional spaces of fence offset
  261. i = container.fence_offset;
  262. while (i > 0 && ln.charCodeAt(offset) === C_SPACE) {
  263. offset++;
  264. i--;
  265. }
  266. break;
  267. case 'HtmlBlock':
  268. if (blank) {
  269. container.last_line_blank = true;
  270. all_matched = false;
  271. }
  272. break;
  273. case 'Paragraph':
  274. if (blank) {
  275. container.last_line_blank = true;
  276. all_matched = false;
  277. }
  278. break;
  279. default:
  280. }
  281. if (!all_matched) {
  282. container = container.parent; // back up to last matching block
  283. break;
  284. }
  285. }
  286. last_matched_container = container;
  287. // This function is used to finalize and close any unmatched
  288. // blocks. We aren't ready to do this now, because we might
  289. // have a lazy paragraph continuation, in which case we don't
  290. // want to close unmatched blocks. So we store this closure for
  291. // use later, when we have more information.
  292. var closeUnmatchedBlocks = function(mythis) {
  293. // finalize any blocks not matched
  294. while (oldtip !== last_matched_container) {
  295. mythis.finalize(oldtip, line_number - 1);
  296. oldtip = oldtip.parent;
  297. }
  298. };
  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, line_number);
  302. }
  303. // Unless last matched container is a code block, try new container starts,
  304. // adding children to the last matched container:
  305. while (container.t !== 'FencedCode' &&
  306. container.t !== 'IndentedCode' &&
  307. container.t !== 'HtmlBlock' &&
  308. // this is a little performance optimization:
  309. matchAt(reMaybeSpecial, ln, offset) !== -1) {
  310. match = matchAt(reNonSpace, ln, offset);
  311. if (match === -1) {
  312. first_nonspace = ln.length;
  313. blank = true;
  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.t !== 'Paragraph' && !blank) {
  322. offset += CODE_INDENT;
  323. closeUnmatchedBlocks(this);
  324. container = this.addChild('IndentedCode', line_number, offset);
  325. } else { // indent > 4 in a lazy paragraph continuation
  326. break;
  327. }
  328. } else if (ln.charCodeAt(first_nonspace) === C_GREATERTHAN) {
  329. // blockquote
  330. offset = first_nonspace + 1;
  331. // optional following space
  332. if (ln.charCodeAt(offset) === C_SPACE) {
  333. offset++;
  334. }
  335. closeUnmatchedBlocks(this);
  336. container = this.addChild('BlockQuote', line_number, offset);
  337. } else if ((match = ln.slice(first_nonspace).match(reATXHeaderMarker))) {
  338. // ATX header
  339. offset = first_nonspace + match[0].length;
  340. closeUnmatchedBlocks(this);
  341. container = this.addChild('Header', line_number, first_nonspace);
  342. container.level = match[0].trim().length; // number of #s
  343. // remove trailing ###s:
  344. container.strings =
  345. [ln.slice(offset).replace(/^ *#+ *$/, '').replace(/ +#+ *$/, '')];
  346. break;
  347. } else if ((match = ln.slice(first_nonspace).match(reCodeFence))) {
  348. // fenced code block
  349. var fence_length = match[0].length;
  350. closeUnmatchedBlocks(this);
  351. container = this.addChild('FencedCode', line_number, first_nonspace);
  352. container.fence_length = fence_length;
  353. container.fence_char = match[0][0];
  354. container.fence_offset = first_nonspace - offset;
  355. offset = first_nonspace + fence_length;
  356. break;
  357. } else if (matchAt(reHtmlBlockOpen, ln, first_nonspace) !== -1) {
  358. // html block
  359. closeUnmatchedBlocks(this);
  360. container = this.addChild('HtmlBlock', line_number, first_nonspace);
  361. // note, we don't adjust offset because the tag is part of the text
  362. break;
  363. } else if (container.t === 'Paragraph' &&
  364. container.strings.length === 1 &&
  365. ((match = ln.slice(first_nonspace).match(reSetextHeaderLine)))) {
  366. // setext header line
  367. closeUnmatchedBlocks(this);
  368. container.t = 'Header'; // convert Paragraph to SetextHeader
  369. container.level = match[0][0] === '=' ? 1 : 2;
  370. offset = ln.length;
  371. } else if (matchAt(reHrule, ln, first_nonspace) !== -1) {
  372. // hrule
  373. closeUnmatchedBlocks(this);
  374. container = this.addChild('HorizontalRule', line_number, first_nonspace);
  375. offset = ln.length - 1;
  376. break;
  377. } else if ((data = parseListMarker(ln, first_nonspace))) {
  378. // list item
  379. closeUnmatchedBlocks(this);
  380. data.marker_offset = indent;
  381. offset = first_nonspace + data.padding;
  382. // add the list if needed
  383. if (container.t !== 'List' ||
  384. !(listsMatch(container.list_data, data))) {
  385. container = this.addChild('List', line_number, first_nonspace);
  386. container.list_data = data;
  387. }
  388. // add the list item
  389. container = this.addChild('Item', line_number, first_nonspace);
  390. container.list_data = data;
  391. } else {
  392. break;
  393. }
  394. if (acceptsLines(container.t)) {
  395. // if it's a line container, it can't contain other containers
  396. break;
  397. }
  398. }
  399. // What remains at the offset is a text line. Add the text to the
  400. // appropriate container.
  401. match = matchAt(reNonSpace, ln, offset);
  402. if (match === -1) {
  403. first_nonspace = ln.length;
  404. blank = true;
  405. } else {
  406. first_nonspace = match;
  407. blank = false;
  408. }
  409. indent = first_nonspace - offset;
  410. // First check for a lazy paragraph continuation:
  411. if (this.tip !== last_matched_container &&
  412. !blank &&
  413. this.tip.t === 'Paragraph' &&
  414. this.tip.strings.length > 0) {
  415. // lazy paragraph continuation
  416. this.last_line_blank = false;
  417. this.addLine(ln, offset);
  418. } else { // not a lazy continuation
  419. // finalize any blocks not matched
  420. closeUnmatchedBlocks(this);
  421. // Block quote lines are never blank as they start with >
  422. // and we don't count blanks in fenced code for purposes of tight/loose
  423. // lists or breaking out of lists. We also don't set last_line_blank
  424. // on an empty list item.
  425. container.last_line_blank = blank &&
  426. !(container.t === 'BlockQuote' ||
  427. container.t === 'Header' ||
  428. container.t === 'FencedCode' ||
  429. (container.t === 'Item' &&
  430. !container.firstChild &&
  431. container.sourcepos[0][0] === line_number));
  432. var cont = container;
  433. while (cont.parent) {
  434. cont.parent.last_line_blank = false;
  435. cont = cont.parent;
  436. }
  437. switch (container.t) {
  438. case 'IndentedCode':
  439. case 'HtmlBlock':
  440. this.addLine(ln, offset);
  441. break;
  442. case 'FencedCode':
  443. // check for closing code fence:
  444. match = (indent <= 3 &&
  445. ln.charAt(first_nonspace) === container.fence_char &&
  446. ln.slice(first_nonspace).match(reClosingCodeFence));
  447. if (match && match[0].length >= container.fence_length) {
  448. // don't add closing fence to container; instead, close it:
  449. this.finalize(container, line_number);
  450. } else {
  451. this.addLine(ln, offset);
  452. }
  453. break;
  454. case 'Header':
  455. case 'HorizontalRule':
  456. // nothing to do; we already added the contents.
  457. break;
  458. default:
  459. if (acceptsLines(container.t)) {
  460. this.addLine(ln, first_nonspace);
  461. } else if (blank) {
  462. break;
  463. } else {
  464. // create paragraph container for line
  465. container = this.addChild('Paragraph', line_number, first_nonspace);
  466. this.addLine(ln, first_nonspace);
  467. }
  468. }
  469. }
  470. this.lastLineLength = ln.length - 1; // -1 for newline
  471. };
  472. // Finalize a block. Close it and do any necessary postprocessing,
  473. // e.g. creating string_content from strings, setting the 'tight'
  474. // or 'loose' status of a list, and parsing the beginnings
  475. // of paragraphs for reference definitions. Reset the tip to the
  476. // parent of the closed block.
  477. var finalize = function(block, line_number) {
  478. var pos;
  479. // don't do anything if the block is already closed
  480. if (!block.open) {
  481. return 0;
  482. }
  483. block.open = false;
  484. block.sourcepos[1] = [line_number, this.lastLineLength + 1];
  485. switch (block.t) {
  486. case 'Paragraph':
  487. block.string_content = block.strings.join('\n');
  488. // try parsing the beginning as link reference definitions:
  489. while (block.string_content.charCodeAt(0) === C_OPEN_BRACKET &&
  490. (pos = this.inlineParser.parseReference(block.string_content,
  491. this.refmap))) {
  492. block.string_content = block.string_content.slice(pos);
  493. if (isBlank(block.string_content)) {
  494. block.t = 'ReferenceDef';
  495. break;
  496. }
  497. }
  498. break;
  499. case 'Header':
  500. block.string_content = block.strings.join('\n');
  501. break;
  502. case 'HtmlBlock':
  503. block.literal = block.strings.join('\n');
  504. break;
  505. case 'IndentedCode':
  506. stripFinalBlankLines(block.strings);
  507. block.literal = block.strings.join('\n') + '\n';
  508. block.t = 'CodeBlock';
  509. break;
  510. case 'FencedCode':
  511. // first line becomes info string
  512. block.info = unescapeString(block.strings[0].trim());
  513. if (block.strings.length === 1) {
  514. block.literal = '';
  515. } else {
  516. block.literal = block.strings.slice(1).join('\n') + '\n';
  517. }
  518. block.t = 'CodeBlock';
  519. break;
  520. case 'List':
  521. block.list_data.tight = true; // tight by default
  522. var item = block.firstChild;
  523. while (item) {
  524. // check for non-final list item ending with blank line:
  525. if (endsWithBlankLine(item) && item.next) {
  526. block.list_data.tight = false;
  527. break;
  528. }
  529. // recurse into children of list item, to see if there are
  530. // spaces between any of them:
  531. var subitem = item.firstChild;
  532. while (subitem) {
  533. if (endsWithBlankLine(subitem) && (item.next || subitem.next)) {
  534. block.list_data.tight = false;
  535. break;
  536. }
  537. subitem = subitem.next;
  538. }
  539. item = item.next;
  540. }
  541. break;
  542. default:
  543. break;
  544. }
  545. this.tip = block.parent || this.top;
  546. };
  547. // Walk through a block & children recursively, parsing string content
  548. // into inline content where appropriate. Returns new object.
  549. var processInlines = function(block) {
  550. var node, event;
  551. var walker = block.walker();
  552. while ((event = walker.next())) {
  553. node = event.node;
  554. if (!event.entering && (node.t === 'Paragraph' ||
  555. node.t === 'Header')) {
  556. this.inlineParser.parse(node, this.refmap);
  557. }
  558. }
  559. };
  560. var Document = function() {
  561. var doc = new Node('Document', [[1, 1], [0, 0]]);
  562. doc.string_content = undefined;
  563. doc.strings = [];
  564. return doc;
  565. };
  566. // The main parsing function. Returns a parsed document AST.
  567. var parse = function(input) {
  568. this.doc = new Document();
  569. this.tip = this.doc;
  570. this.refmap = {};
  571. if (this.options.time) { console.time("preparing input"); }
  572. var lines = input.split(reLineEnding);
  573. var len = lines.length;
  574. if (input.charCodeAt(input.length - 1) === C_NEWLINE) {
  575. // ignore last blank line created by final newline
  576. len -= 1;
  577. }
  578. if (this.options.time) { console.timeEnd("preparing input"); }
  579. if (this.options.time) { console.time("block parsing"); }
  580. for (var i = 0; i < len; i++) {
  581. this.incorporateLine(lines[i], i + 1);
  582. }
  583. while (this.tip) {
  584. this.finalize(this.tip, len);
  585. }
  586. if (this.options.time) { console.timeEnd("block parsing"); }
  587. if (this.options.time) { console.time("inline parsing"); }
  588. this.processInlines(this.doc);
  589. if (this.options.time) { console.timeEnd("inline parsing"); }
  590. return this.doc;
  591. };
  592. // The DocParser object.
  593. function DocParser(options){
  594. return {
  595. doc: new Document(),
  596. tip: this.doc,
  597. refmap: {},
  598. lastLineLength: 0,
  599. inlineParser: new InlineParser(),
  600. breakOutOfLists: breakOutOfLists,
  601. addLine: addLine,
  602. addChild: addChild,
  603. incorporateLine: incorporateLine,
  604. finalize: finalize,
  605. processInlines: processInlines,
  606. parse: parse,
  607. options: options || {}
  608. };
  609. }
  610. module.exports = DocParser;