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