aboutsummaryrefslogtreecommitdiff
path: root/src/blocks.c
blob: ae106d258038d86e3a2384b5c952bbb90bc9664c (plain)
  1. #include <stdlib.h>
  2. #include <assert.h>
  3. #include <stdio.h>
  4. #include <stdbool.h>
  5. #include <ctype.h>
  6. #include "cmark.h"
  7. #include "utf8.h"
  8. #include "scanners.h"
  9. #include "inlines.h"
  10. #include "html/houdini.h"
  11. #define peek_at(i, n) (i)->data[n]
  12. static void incorporate_line(strbuf *ln, int line_number, node_block** curptr);
  13. static void finalize(node_block* b, int line_number);
  14. static node_block* make_block(int tag, int start_line, int start_column)
  15. {
  16. node_block* e;
  17. e = calloc(1, sizeof(*e));
  18. if(e != NULL) {
  19. e->tag = tag;
  20. e->open = true;
  21. e->start_line = start_line;
  22. e->start_column = start_column;
  23. e->end_line = start_line;
  24. strbuf_init(&e->string_content, 32);
  25. }
  26. return e;
  27. }
  28. // Create a root document node_block.
  29. extern node_block* make_document()
  30. {
  31. node_block *e = make_block(BLOCK_DOCUMENT, 1, 1);
  32. e->as.document.refmap = reference_map_new();
  33. e->top = e;
  34. return e;
  35. }
  36. // Returns true if line has only space characters, else false.
  37. bool is_blank(strbuf *s, int offset)
  38. {
  39. while (offset < s->size) {
  40. switch (s->ptr[offset]) {
  41. case '\n':
  42. return true;
  43. case ' ':
  44. offset++;
  45. break;
  46. default:
  47. return false;
  48. }
  49. }
  50. return true;
  51. }
  52. static inline bool can_contain(int parent_type, int child_type)
  53. {
  54. return ( parent_type == BLOCK_DOCUMENT ||
  55. parent_type == BLOCK_BQUOTE ||
  56. parent_type == BLOCK_LIST_ITEM ||
  57. (parent_type == BLOCK_LIST && child_type == BLOCK_LIST_ITEM) );
  58. }
  59. static inline bool accepts_lines(int block_type)
  60. {
  61. return (block_type == BLOCK_PARAGRAPH ||
  62. block_type == BLOCK_ATX_HEADER ||
  63. block_type == BLOCK_INDENTED_CODE ||
  64. block_type == BLOCK_FENCED_CODE);
  65. }
  66. static void add_line(node_block* node_block, chunk *ch, int offset)
  67. {
  68. assert(node_block->open);
  69. strbuf_put(&node_block->string_content, ch->data + offset, ch->len - offset);
  70. }
  71. static void remove_trailing_blank_lines(strbuf *ln)
  72. {
  73. int i;
  74. for (i = ln->size - 1; i >= 0; --i) {
  75. unsigned char c = ln->ptr[i];
  76. if (c != ' ' && c != '\t' && c != '\r' && c != '\n')
  77. break;
  78. }
  79. if (i < 0) {
  80. strbuf_clear(ln);
  81. return;
  82. }
  83. i = strbuf_strchr(ln, '\n', i);
  84. if (i >= 0)
  85. strbuf_truncate(ln, i);
  86. }
  87. // Check to see if a node_block ends with a blank line, descending
  88. // if needed into lists and sublists.
  89. static bool ends_with_blank_line(node_block* node_block)
  90. {
  91. if (node_block->last_line_blank) {
  92. return true;
  93. }
  94. if ((node_block->tag == BLOCK_LIST || node_block->tag == BLOCK_LIST_ITEM) && node_block->last_child) {
  95. return ends_with_blank_line(node_block->last_child);
  96. } else {
  97. return false;
  98. }
  99. }
  100. // Break out of all containing lists
  101. static int break_out_of_lists(node_block ** bptr, int line_number)
  102. {
  103. node_block *container = *bptr;
  104. node_block *b = container->top;
  105. // find first containing BLOCK_LIST:
  106. while (b && b->tag != BLOCK_LIST) {
  107. b = b->last_child;
  108. }
  109. if (b) {
  110. while (container && container != b) {
  111. finalize(container, line_number);
  112. container = container->parent;
  113. }
  114. finalize(b, line_number);
  115. *bptr = b->parent;
  116. }
  117. return 0;
  118. }
  119. static void finalize(node_block* b, int line_number)
  120. {
  121. int firstlinelen;
  122. int pos;
  123. node_block* item;
  124. node_block* subitem;
  125. if (!b->open)
  126. return; // don't do anything if the node_block is already closed
  127. b->open = false;
  128. if (line_number > b->start_line) {
  129. b->end_line = line_number - 1;
  130. } else {
  131. b->end_line = line_number;
  132. }
  133. switch (b->tag) {
  134. case BLOCK_PARAGRAPH:
  135. pos = 0;
  136. while (strbuf_at(&b->string_content, 0) == '[' &&
  137. (pos = parse_reference_inline(&b->string_content, b->top->as.document.refmap))) {
  138. strbuf_drop(&b->string_content, pos);
  139. }
  140. if (is_blank(&b->string_content, 0)) {
  141. b->tag = BLOCK_REFERENCE_DEF;
  142. }
  143. break;
  144. case BLOCK_INDENTED_CODE:
  145. remove_trailing_blank_lines(&b->string_content);
  146. strbuf_putc(&b->string_content, '\n');
  147. break;
  148. case BLOCK_FENCED_CODE:
  149. // first line of contents becomes info
  150. firstlinelen = strbuf_strchr(&b->string_content, '\n', 0);
  151. strbuf_init(&b->as.code.info, 0);
  152. houdini_unescape_html_f(
  153. &b->as.code.info,
  154. b->string_content.ptr,
  155. firstlinelen
  156. );
  157. strbuf_drop(&b->string_content, firstlinelen + 1);
  158. strbuf_trim(&b->as.code.info);
  159. strbuf_unescape(&b->as.code.info);
  160. break;
  161. case BLOCK_LIST: // determine tight/loose status
  162. b->as.list.tight = true; // tight by default
  163. item = b->children;
  164. while (item) {
  165. // check for non-final non-empty list item ending with blank line:
  166. if (item->last_line_blank && item->next) {
  167. b->as.list.tight = false;
  168. break;
  169. }
  170. // recurse into children of list item, to see if there are
  171. // spaces between them:
  172. subitem = item->children;
  173. while (subitem) {
  174. if (ends_with_blank_line(subitem) &&
  175. (item->next || subitem->next)) {
  176. b->as.list.tight = false;
  177. break;
  178. }
  179. subitem = subitem->next;
  180. }
  181. if (!(b->as.list.tight)) {
  182. break;
  183. }
  184. item = item->next;
  185. }
  186. break;
  187. default:
  188. break;
  189. }
  190. }
  191. // Add a node_block as child of another. Return pointer to child.
  192. static node_block* add_child(node_block* parent,
  193. int block_type, int start_line, int start_column)
  194. {
  195. assert(parent);
  196. // if 'parent' isn't the kind of node_block that can accept this child,
  197. // then back up til we hit a node_block that can.
  198. while (!can_contain(parent->tag, block_type)) {
  199. finalize(parent, start_line);
  200. parent = parent->parent;
  201. }
  202. node_block* child = make_block(block_type, start_line, start_column);
  203. child->parent = parent;
  204. child->top = parent->top;
  205. if (parent->last_child) {
  206. parent->last_child->next = child;
  207. child->prev = parent->last_child;
  208. } else {
  209. parent->children = child;
  210. child->prev = NULL;
  211. }
  212. parent->last_child = child;
  213. return child;
  214. }
  215. // Free a node_block list and any children.
  216. void cmark_free_nodes(node_block *e)
  217. {
  218. node_block * next;
  219. while (e != NULL) {
  220. next = e->next;
  221. free_inlines(e->inline_content);
  222. strbuf_free(&e->string_content);
  223. if (e->tag == BLOCK_FENCED_CODE) {
  224. strbuf_free(&e->as.code.info);
  225. } else if (e->tag == BLOCK_DOCUMENT) {
  226. reference_map_free(e->as.document.refmap);
  227. }
  228. cmark_free_nodes(e->children);
  229. free(e);
  230. e = next;
  231. }
  232. }
  233. // Walk through node_block and all children, recursively, parsing
  234. // string content into inline content where appropriate.
  235. void process_inlines(node_block* cur, reference_map *refmap)
  236. {
  237. switch (cur->tag) {
  238. case BLOCK_PARAGRAPH:
  239. case BLOCK_ATX_HEADER:
  240. case BLOCK_SETEXT_HEADER:
  241. cur->inline_content = parse_inlines(&cur->string_content, refmap);
  242. break;
  243. default:
  244. break;
  245. }
  246. node_block *child = cur->children;
  247. while (child != NULL) {
  248. process_inlines(child, refmap);
  249. child = child->next;
  250. }
  251. }
  252. // Attempts to parse a list item marker (bullet or enumerated).
  253. // On success, returns length of the marker, and populates
  254. // data with the details. On failure, returns 0.
  255. static int parse_list_marker(chunk *input, int pos, struct ListData ** dataptr)
  256. {
  257. unsigned char c;
  258. int startpos;
  259. struct ListData * data;
  260. startpos = pos;
  261. c = peek_at(input, pos);
  262. if ((c == '*' || c == '-' || c == '+') && !scan_hrule(input, pos)) {
  263. pos++;
  264. if (!isspace(peek_at(input, pos))) {
  265. return 0;
  266. }
  267. data = calloc(1, sizeof(*data));
  268. if(data == NULL) {
  269. return 0;
  270. } else {
  271. data->marker_offset = 0; // will be adjusted later
  272. data->list_type = bullet;
  273. data->bullet_char = c;
  274. data->start = 1;
  275. data->delimiter = period;
  276. data->tight = false;
  277. }
  278. } else if (isdigit(c)) {
  279. int start = 0;
  280. do {
  281. start = (10 * start) + (peek_at(input, pos) - '0');
  282. pos++;
  283. } while (isdigit(peek_at(input, pos)));
  284. c = peek_at(input, pos);
  285. if (c == '.' || c == ')') {
  286. pos++;
  287. if (!isspace(peek_at(input, pos))) {
  288. return 0;
  289. }
  290. data = calloc(1, sizeof(*data));
  291. if(data == NULL) {
  292. return 0;
  293. } else {
  294. data->marker_offset = 0; // will be adjusted later
  295. data->list_type = ordered;
  296. data->bullet_char = 0;
  297. data->start = start;
  298. data->delimiter = (c == '.' ? period : parens);
  299. data->tight = false;
  300. }
  301. } else {
  302. return 0;
  303. }
  304. } else {
  305. return 0;
  306. }
  307. *dataptr = data;
  308. return (pos - startpos);
  309. }
  310. // Return 1 if list item belongs in list, else 0.
  311. static int lists_match(struct ListData *list_data, struct ListData *item_data)
  312. {
  313. return (list_data->list_type == item_data->list_type &&
  314. list_data->delimiter == item_data->delimiter &&
  315. // list_data->marker_offset == item_data.marker_offset &&
  316. list_data->bullet_char == item_data->bullet_char);
  317. }
  318. static node_block *finalize_document(node_block *document, int linenum)
  319. {
  320. while (document != document->top) {
  321. finalize(document, linenum);
  322. document = document->parent;
  323. }
  324. finalize(document, linenum);
  325. process_inlines(document, document->as.document.refmap);
  326. return document;
  327. }
  328. extern node_block *cmark_parse_file(FILE *f)
  329. {
  330. strbuf line = GH_BUF_INIT;
  331. unsigned char buffer[4096];
  332. int linenum = 1;
  333. node_block *document = make_document();
  334. while (fgets((char *)buffer, sizeof(buffer), f)) {
  335. utf8proc_detab(&line, buffer, strlen((char *)buffer));
  336. incorporate_line(&line, linenum, &document);
  337. strbuf_clear(&line);
  338. linenum++;
  339. }
  340. strbuf_free(&line);
  341. return finalize_document(document, linenum);
  342. }
  343. extern node_block *cmark_parse_document(const unsigned char *buffer, size_t len)
  344. {
  345. strbuf line = GH_BUF_INIT;
  346. int linenum = 1;
  347. const unsigned char *end = buffer + len;
  348. node_block *document = make_document();
  349. while (buffer < end) {
  350. const unsigned char *eol = memchr(buffer, '\n', end - buffer);
  351. if (!eol) {
  352. utf8proc_detab(&line, buffer, end - buffer);
  353. buffer = end;
  354. } else {
  355. utf8proc_detab(&line, buffer, (eol - buffer) + 1);
  356. buffer += (eol - buffer) + 1;
  357. }
  358. incorporate_line(&line, linenum, &document);
  359. strbuf_clear(&line);
  360. linenum++;
  361. }
  362. strbuf_free(&line);
  363. return finalize_document(document, linenum);
  364. }
  365. static void chop_trailing_hashtags(chunk *ch)
  366. {
  367. int n, orig_n;
  368. chunk_rtrim(ch);
  369. orig_n = n = ch->len - 1;
  370. // if string ends in #s, remove these:
  371. while (n >= 0 && peek_at(ch, n) == '#')
  372. n--;
  373. // the last # was escaped, so we include it.
  374. if (n != orig_n && n >= 0 && peek_at(ch, n) == '\\')
  375. n++;
  376. ch->len = n + 1;
  377. }
  378. // Process one line at a time, modifying a node_block.
  379. static void incorporate_line(strbuf *line, int line_number, node_block** curptr)
  380. {
  381. node_block* last_matched_container;
  382. int offset = 0;
  383. int matched = 0;
  384. int lev = 0;
  385. int i;
  386. struct ListData * data = NULL;
  387. bool all_matched = true;
  388. node_block* container;
  389. node_block* cur = *curptr;
  390. bool blank = false;
  391. int first_nonspace;
  392. int indent;
  393. chunk input;
  394. // Add a newline to the end if not present:
  395. if (line->ptr[line->size - 1] != '\n') {
  396. strbuf_putc(line, '\n');
  397. }
  398. input.data = line->ptr;
  399. input.len = line->size;
  400. // container starts at the document root.
  401. container = cur->top;
  402. // for each containing node_block, try to parse the associated line start.
  403. // bail out on failure: container will point to the last matching node_block.
  404. while (container->last_child && container->last_child->open) {
  405. container = container->last_child;
  406. first_nonspace = offset;
  407. while (peek_at(&input, first_nonspace) == ' ') {
  408. first_nonspace++;
  409. }
  410. indent = first_nonspace - offset;
  411. blank = peek_at(&input, first_nonspace) == '\n';
  412. if (container->tag == BLOCK_BQUOTE) {
  413. matched = indent <= 3 && peek_at(&input, first_nonspace) == '>';
  414. if (matched) {
  415. offset = first_nonspace + 1;
  416. if (peek_at(&input, offset) == ' ')
  417. offset++;
  418. } else {
  419. all_matched = false;
  420. }
  421. } else if (container->tag == BLOCK_LIST_ITEM) {
  422. if (indent >= container->as.list.marker_offset +
  423. container->as.list.padding) {
  424. offset += container->as.list.marker_offset +
  425. container->as.list.padding;
  426. } else if (blank) {
  427. offset = first_nonspace;
  428. } else {
  429. all_matched = false;
  430. }
  431. } else if (container->tag == BLOCK_INDENTED_CODE) {
  432. if (indent >= CODE_INDENT) {
  433. offset += CODE_INDENT;
  434. } else if (blank) {
  435. offset = first_nonspace;
  436. } else {
  437. all_matched = false;
  438. }
  439. } else if (container->tag == BLOCK_ATX_HEADER ||
  440. container->tag == BLOCK_SETEXT_HEADER) {
  441. // a header can never contain more than one line
  442. all_matched = false;
  443. } else if (container->tag == BLOCK_FENCED_CODE) {
  444. // skip optional spaces of fence offset
  445. i = container->as.code.fence_offset;
  446. while (i > 0 && peek_at(&input, offset) == ' ') {
  447. offset++;
  448. i--;
  449. }
  450. } else if (container->tag == BLOCK_HTML) {
  451. if (blank) {
  452. all_matched = false;
  453. }
  454. } else if (container->tag == BLOCK_PARAGRAPH) {
  455. if (blank) {
  456. container->last_line_blank = true;
  457. all_matched = false;
  458. }
  459. }
  460. if (!all_matched) {
  461. container = container->parent; // back up to last matching node_block
  462. break;
  463. }
  464. }
  465. last_matched_container = container;
  466. // check to see if we've hit 2nd blank line, break out of list:
  467. if (blank && container->last_line_blank) {
  468. break_out_of_lists(&container, line_number);
  469. }
  470. // unless last matched container is code node_block, try new container starts:
  471. while (container->tag != BLOCK_FENCED_CODE && container->tag != BLOCK_INDENTED_CODE &&
  472. container->tag != BLOCK_HTML) {
  473. first_nonspace = offset;
  474. while (peek_at(&input, first_nonspace) == ' ')
  475. first_nonspace++;
  476. indent = first_nonspace - offset;
  477. blank = peek_at(&input, first_nonspace) == '\n';
  478. if (indent >= CODE_INDENT) {
  479. if (cur->tag != BLOCK_PARAGRAPH && !blank) {
  480. offset += CODE_INDENT;
  481. container = add_child(container, BLOCK_INDENTED_CODE, line_number, offset + 1);
  482. } else { // indent > 4 in lazy line
  483. break;
  484. }
  485. } else if (peek_at(&input, first_nonspace) == '>') {
  486. offset = first_nonspace + 1;
  487. // optional following character
  488. if (peek_at(&input, offset) == ' ')
  489. offset++;
  490. container = add_child(container, BLOCK_BQUOTE, line_number, offset + 1);
  491. } else if ((matched = scan_atx_header_start(&input, first_nonspace))) {
  492. offset = first_nonspace + matched;
  493. container = add_child(container, BLOCK_ATX_HEADER, line_number, offset + 1);
  494. int hashpos = chunk_strchr(&input, '#', first_nonspace);
  495. int level = 0;
  496. while (peek_at(&input, hashpos) == '#') {
  497. level++;
  498. hashpos++;
  499. }
  500. container->as.header.level = level;
  501. } else if ((matched = scan_open_code_fence(&input, first_nonspace))) {
  502. container = add_child(container, BLOCK_FENCED_CODE, line_number, first_nonspace + 1);
  503. container->as.code.fence_char = peek_at(&input, first_nonspace);
  504. container->as.code.fence_length = matched;
  505. container->as.code.fence_offset = first_nonspace - offset;
  506. offset = first_nonspace + matched;
  507. } else if ((matched = scan_html_block_tag(&input, first_nonspace))) {
  508. container = add_child(container, BLOCK_HTML, line_number, first_nonspace + 1);
  509. // note, we don't adjust offset because the tag is part of the text
  510. } else if (container->tag == BLOCK_PARAGRAPH &&
  511. (lev = scan_setext_header_line(&input, first_nonspace)) &&
  512. // check that there is only one line in the paragraph:
  513. strbuf_strrchr(&container->string_content, '\n',
  514. strbuf_len(&container->string_content) - 2) < 0) {
  515. container->tag = BLOCK_SETEXT_HEADER;
  516. container->as.header.level = lev;
  517. offset = input.len - 1;
  518. } else if (!(container->tag == BLOCK_PARAGRAPH && !all_matched) &&
  519. (matched = scan_hrule(&input, first_nonspace))) {
  520. // it's only now that we know the line is not part of a setext header:
  521. container = add_child(container, BLOCK_HRULE, line_number, first_nonspace + 1);
  522. finalize(container, line_number);
  523. container = container->parent;
  524. offset = input.len - 1;
  525. } else if ((matched = parse_list_marker(&input, first_nonspace, &data))) {
  526. // compute padding:
  527. offset = first_nonspace + matched;
  528. i = 0;
  529. while (i <= 5 && peek_at(&input, offset + i) == ' ') {
  530. i++;
  531. }
  532. // i = number of spaces after marker, up to 5
  533. if (i >= 5 || i < 1 || peek_at(&input, offset) == '\n') {
  534. data->padding = matched + 1;
  535. if (i > 0) {
  536. offset += 1;
  537. }
  538. } else {
  539. data->padding = matched + i;
  540. offset += i;
  541. }
  542. // check container; if it's a list, see if this list item
  543. // can continue the list; otherwise, create a list container.
  544. data->marker_offset = indent;
  545. if (container->tag != BLOCK_LIST ||
  546. !lists_match(&container->as.list, data)) {
  547. container = add_child(container, BLOCK_LIST, line_number,
  548. first_nonspace + 1);
  549. memcpy(&container->as.list, data, sizeof(*data));
  550. }
  551. // add the list item
  552. container = add_child(container, BLOCK_LIST_ITEM, line_number,
  553. first_nonspace + 1);
  554. /* TODO: static */
  555. memcpy(&container->as.list, data, sizeof(*data));
  556. free(data);
  557. } else {
  558. break;
  559. }
  560. if (accepts_lines(container->tag)) {
  561. // if it's a line container, it can't contain other containers
  562. break;
  563. }
  564. }
  565. // what remains at offset is a text line. add the text to the
  566. // appropriate container.
  567. first_nonspace = offset;
  568. while (peek_at(&input, first_nonspace) == ' ')
  569. first_nonspace++;
  570. indent = first_nonspace - offset;
  571. blank = peek_at(&input, first_nonspace) == '\n';
  572. // node_block quote lines are never blank as they start with >
  573. // and we don't count blanks in fenced code for purposes of tight/loose
  574. // lists or breaking out of lists. we also don't set last_line_blank
  575. // on an empty list item.
  576. container->last_line_blank = (blank &&
  577. container->tag != BLOCK_BQUOTE &&
  578. container->tag != BLOCK_FENCED_CODE &&
  579. !(container->tag == BLOCK_LIST_ITEM &&
  580. container->children == NULL &&
  581. container->start_line == line_number));
  582. node_block *cont = container;
  583. while (cont->parent) {
  584. cont->parent->last_line_blank = false;
  585. cont = cont->parent;
  586. }
  587. if (cur != last_matched_container &&
  588. container == last_matched_container &&
  589. !blank &&
  590. cur->tag == BLOCK_PARAGRAPH &&
  591. strbuf_len(&cur->string_content) > 0) {
  592. add_line(cur, &input, offset);
  593. } else { // not a lazy continuation
  594. // finalize any blocks that were not matched and set cur to container:
  595. while (cur != last_matched_container) {
  596. finalize(cur, line_number);
  597. cur = cur->parent;
  598. assert(cur != NULL);
  599. }
  600. if (container->tag == BLOCK_INDENTED_CODE) {
  601. add_line(container, &input, offset);
  602. } else if (container->tag == BLOCK_FENCED_CODE) {
  603. matched = 0;
  604. if (indent <= 3 &&
  605. peek_at(&input, first_nonspace) == container->as.code.fence_char) {
  606. int fence_len = scan_close_code_fence(&input, first_nonspace);
  607. if (fence_len > container->as.code.fence_length)
  608. matched = 1;
  609. }
  610. if (matched) {
  611. // if closing fence, don't add line to container; instead, close it:
  612. finalize(container, line_number);
  613. container = container->parent; // back up to parent
  614. } else {
  615. add_line(container, &input, offset);
  616. }
  617. } else if (container->tag == BLOCK_HTML) {
  618. add_line(container, &input, offset);
  619. } else if (blank) {
  620. // ??? do nothing
  621. } else if (container->tag == BLOCK_ATX_HEADER) {
  622. chop_trailing_hashtags(&input);
  623. add_line(container, &input, first_nonspace);
  624. finalize(container, line_number);
  625. container = container->parent;
  626. } else if (accepts_lines(container->tag)) {
  627. add_line(container, &input, first_nonspace);
  628. } else if (container->tag != BLOCK_HRULE && container->tag != BLOCK_SETEXT_HEADER) {
  629. // create paragraph container for line
  630. container = add_child(container, BLOCK_PARAGRAPH, line_number, first_nonspace + 1);
  631. add_line(container, &input, first_nonspace);
  632. } else {
  633. assert(false);
  634. }
  635. *curptr = container;
  636. }
  637. }