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