/* * A lexer for the _block_ (ie, vertical) component of Markdown. * * This file is part of Beastie * SPDX-FileCopyrightText: 2023 Norman Gray * SPDX-License-Identifier: BSD-2-Clause */ %top{ #if __GNUC__ && !defined(__clang__) // for fileno #define _XOPEN_SOURCE 600 #endif } %{ /* * Notes on the lexing of Markdown. * * I've tended to follow the syntax description in the original * Markdown spec, at . * This is vague in places, but is vague in a way which matches its * general ‘do what I mean’ attitude. * * In particular: * * - I currently ignore HTML completely. * - In the Gruber spec, ‘indented’ means ‘four spaces or a tab’, * and there's no indication of what, say, a two-space indent * might mean. * - Gruber says that only the first line of a blockquote has to be * prefixed; the following requires all lines in a blockquote to be prefixed. * - The Gruber spec doesn't mention sublists, but almost every * other markdown parser supports them (except this one, so far). * - This doesn't support code blocks inside list items (but that * . would probably be part of a what-do-I-do-with-double-indent question. */ #include "config.h" #include #include #if HAVE_ALLOCA_H #include #endif #include "beastie.h" #include "util.h" #include "parse-markdown.h" #include "parse-markdown.tab.h" #ifndef WITH_MAIN #define WITH_MAIN 0 #endif // GC protection #define GCP(x) s7_gc_protect_via_stack(S7, x) /* If vspace_p is true, then reset it to false, push the contents * back into the stream, and return BLANK */ #define MAYBEBLANK do { \ if (yyextra->vspace_p) { \ yyextra->vspace_p = 0; \ yyless(0); \ return BLANK; \ } \ } while(0) /* Return either a or b, depending on whether vspace_p is true or false */ #define IFSPACE(a, b) (yyextra->vspace_p ? (yyextra->vspace_p = 0, a) : b) /* The buffer bstart is of length blen, and ends with '\n'. * Create an s7 string from p, pointing within the string, to the end, * omitting the trailing newline. */ #define LVALFROM(bstart, p, blen) do { \ *yylval = string_from_buf(bstart, p, blen); \ } while (0) /* Make (cons a/symbol b) */ #define MAKE_CONS(a, b) s7_cons(S7, s7_make_symbol(S7, a), b) /* defined in parse-markdown.y */ extern int markdowndebug; static s7_pointer string_from_buf(const char* buf_start, const char* p, const size_t blen); %} %option prefix="markdown" reentrant bison-bridge bison-locations %option noyywrap nounput yylineno debug %option extra-type="markdown_extra_t" /* Flex doesn't do Unicode. There is a alternative lexer RE-flex * which does and which might * be of interest in the future, but for now, we have to do it by * hand. The following patterns were taken from a Stackoverflow * answer by ‘Kaz’, * * These patters work by spotting UTF-8 byte patterns. * They therefore cover only UTF-8. * That's mostly OK here, because s7's unicode support is actually * just UTF-8 support. and it handles the decoding of the UTF-8 * strings we lex here, so we don't have to. * * ASCN and UANYN are ASC and UANY minus newline. * UONLY is non-ASCII. */ ASC [\x00-\x7f] ASCN [\x00-\t\v-\x7f] U [\x80-\xbf] U2 [\xc2-\xdf] U3 [\xe0-\xef] U4 [\xf0-\xf4] UANY {ASC}|{U2}{U}|{U3}{U}{U}|{U4}{U}{U}{U} UANYN {ASCN}|{U2}{U}|{U3}{U}{U}|{U4}{U}{U}{U} UONLY {U2}{U}|{U3}{U}{U}|{U4}{U}{U}{U} ORDINARY [^>#=[:space:]-] NUMBER [0-9] HWS [ \t] BULLET [*+-] /* Markdown spec: * * Link definition names may consist of letters, numbers, spaces, and punctuation * -- but they are not case sensitive. * * Ie, terminally vague as usual: * I've chosen the 'punctuation' here to be ispunct(3) minus ["'<>\]. * * Not mentioned in the Markdown spec is what we do with non-ASCII content. * I think that I should allow any non-ASCII Unicode here. */ LINKREF ({UONLY}|[ a-zA-Z0-9!#$%&()*+,./:;=?@^_{|}~-])+ /* I'm supporting metadata keys as an extension. * The [YAML spec](https://yaml.org/spec/1.2.2/) is useless: * Sect.7.3.3 purports to explain what ‘plain style’ map keys are, * and makes a typical dog's breakfast of it. * I'm taking it to be anything non-ASCII, * plus anything ASCII-alphanumeric + space, plus dash, * because the excess generality of YAML is bloody silly. */ METADATAKEY ({UONLY}|[a-zA-Z0-9 -])+ /* State BQ: we are in a '> ...' blockquoted context */ %s BQ %x METADATA %% [=]+"\n" return H1UNDERLINE; /* A "---" line might be an H2UNDERLINE, or it may be prefacing YAML. * The only YAML we recognise is "key: value" pairs. * * Include MAYBEBLANK here, since we want to distinguish * between a line immediately followed by '---', * which is an H2 heading, * from a paragraph followed by a blank line and '---', * which is a horizontal-rule. */ [-]+"\n" { MAYBEBLANK; BEGIN(METADATA); yyextra->found_annotation_p = 0; } /* Markdown supports '- - -' or '* * *' as rules, but not a mixture. */ "-"[ -]{3,}"\n" return HR; "*"[ *]{3,}"\n" return HR; {METADATAKEY}":"[[:space:]]+.*"\n" { const char* colon = strchr(yytext, ':'); const char* value = colon + 1; while (isspace(*value)) value++; *yylval = scheme_make_list(s7_make_string_with_length(S7, yytext, colon-yytext), s7_make_string_with_length(S7, value, yyleng-(value-yytext)-1), NULL); yyextra->found_annotation_p = 1; return ANNOTATION; } (.|"\n") { yyless(0); BEGIN(INITIAL); if (yyextra->found_annotation_p) { return BLANK; } else { // no, the "---" was an underline, after all return H2UNDERLINE; } } /* ### headings */ [#]+{HWS}*.+"\n" { MAYBEBLANK; const char* p = yytext; while (*p == '#') p++; const char* pfx_end = p; while (isspace(*p)) p++; // we also want to strip off trailing '#', so can't just use string_from_buf const char* endp = &yytext[yyleng-1]; while ((*endp == '#' || isspace(*endp)) && endp > yytext) endp--; if (endp == yytext) { // ooops: this 'heading' has no actual text in it, so bail out LVALFROM(yytext, yytext, yyleng); return TEXT; } // endp now points at the last non-discarded character size_t len = endp-p+1; char* buf = alloca(len+1); memcpy(buf, p, len); buf[len] = '\0'; int prefix_len = pfx_end - yytext; *yylval = s7_cons(S7, s7_make_integer(S7, (prefix_len > 6 ? 6 : prefix_len)), s7_make_string_with_length(S7, buf, len)); return HN; } /* For both UL and OL list items, we return a pair consisting of a * symbol and a string, where the symbol is 'ul or 'ol depending on * whether the pattern was `*` or `1.`, and the string is the part * after the leading marker. * * First, `*` list items */ {HWS}*{BULLET}{HWS}+.+"\n" { const char* p = yytext; int nindent = 0; while (isspace(*p)) { if (*p == '\t') { nindent += 4; // count tabs as four spaces for this purpose } else { nindent++; } p++; } // now pointing at {BULLET} p++; while (isspace(*p)) p++; *yylval = scheme_make_list(GCP(s7_make_symbol(S7, "ul")), GCP(scheme_make_list(MAKE_CONS("blank?", IFSPACE(s7_t(S7), s7_f(S7))), MAKE_CONS("subitem?", (nindent >= 4 ? s7_t(S7) : s7_f(S7))), MAKE_CONS("line-number", s7_make_integer(S7, yyget_lineno(yyscanner))), NULL)), GCP((*p == '\0') ? s7_make_string(S7, "") // slightly odd: a line " *" : string_from_buf(yytext, p, yyleng)), NULL); return ITEM; } /* 1. list items */ {HWS}*{NUMBER}+[.]{HWS}+.+"\n" { const char* p = yytext; int nindent = 0; while (isspace(*p)) { if (*p == '\t') { nindent += 4; } else { nindent++; } p++; } // now pointing at NUMBER while (isdigit(*p)) p++; p++; // step over dot while (isspace(*p)) p++; *yylval = scheme_make_list(GCP(s7_make_symbol(S7, "ol")), GCP(scheme_make_list(MAKE_CONS("blank?", IFSPACE(s7_t(S7), s7_f(S7))), MAKE_CONS("subitem?", (nindent >= 4 ? s7_t(S7) : s7_f(S7))), MAKE_CONS("line-number", s7_make_integer(S7, yyget_lineno(yyscanner))), NULL)), GCP((*p == '\0') ? s7_make_string(S7, "") // slightly odd: a line " 1." : string_from_buf(yytext, p, yyleng)), NULL); return ITEM; } /* indented line; note that the Gruber spec is specific that indents * are four spaces (or one tab) * See also the [ ]{,3}{ORDINARY}.*"\n" semi-fallback line below. */ [ ]{4}.+"\n" { LVALFROM(yytext, &yytext[4], yyleng); return IFSPACE(B_INDENTED, INDENTED); } /* ...and the same for single-tab indents */ "\t".+"\n" { LVALFROM(yytext, &yytext[1], yyleng); return IFSPACE(B_INDENTED, INDENTED); } /* When we first see a line starting /> ?/, shift into state BQ. * Thereafter, gobble /> ?/ and let other rules match, * until we find /> *\n/, which is a blank line, * or / *\n/ which brings us out of BQ mode. * The ordering of the following lines matters! * * Note: this doesn't cope with nested blockquotes, though I'm sure that with a * suitable counter it wouldn't be too hard to add that. */ {HWS}*"\n" { //fprintf(stderr, "HWS: bq_level=%d\n", yyextra->bq_level); --yyextra->bq_level; if (yyextra->bq_level > 0) { yyless(0); } else { BEGIN(INITIAL); yyextra->vspace_p = 0; } return BLOCKQUOTEEND; } /* quoted blank line */ ">"{HWS}*"\n" yyextra->vspace_p = 1; /* If we see '>' when start-condition is BQ, then we test the value of bq_level. * If the level hasn't changed, then we do nothing. * If it has, then we emit blockquote start or end lexemes as appropriate. * Should we permit more than one space after a ">" (or between them)? */ ">"([ ]*">")*[ ]? { int nindent = 0; for (int i=0; i') nindent++; //fprintf(stderr, "\">\": yytext='%s' nindent=%d bq_level=%d\n", yytext, nindent, yyextra->bq_level); if (nindent != yyextra->bq_level) { if (nindent < yyextra->bq_level) { --yyextra->bq_level; yyless(0); // come back soon! return BLOCKQUOTEEND; } else { ++yyextra->bq_level; yyless(0); return BLOCKQUOTESTART; } } // else do nothing } /* enter blockquote mode: we may have more than one '>' on the line, * if we're jumping straight in to multiple levels of quotation */ (">"[ ]?)+ { int nindent = 0; for (int i=0; i') nindent++; BEGIN(BQ); yyextra->vspace_p = 0; yyextra->bq_level = 1; if (nindent > 1) { // set bq_level to 1, not nindent, and push the content back, // so that the previous rule will increment bq_level while emitting BLOCKQUOTESTART yyless(0); } return BLOCKQUOTESTART; } /* blank line: do nothing, but set a flag which IFSPACE or * MAYBEBLANK will check */ {HWS}*"\n" yyextra->vspace_p = 1; /* spot [ref]: uri 'title', * where the ref matches LINKREF above, * the URI may, but need not, be enclosed in <...>, * and the title may be enclosed in single or double quotes, or parentheses. * I wish flex did submatches! */ [ ]{0,3}"["{LINKREF}"]:"[[:space:]]+[^[:space:]]+.*"\n" { char* p = yytext; while (isspace(*p)) p++; // now pointing at '[' p++; const char* ref = p; while (*p != ']') p++; // note: we do not coerce the link reference to lowercase here, // since it's better to do that in a Unicode-respecting way in parse-markdown.scm // p is now pointing at ']' const char* endref = p; p += 2; // jump over "]:" while (isspace(*p)) p++; // find the URL // sloppy parsing: simply ignore '<' and '>' either side of the URI, // rather than demanding they match if (*p == '<') p++; const char* uri = p; while (!isspace(*p) && *p != '>' && *p != '\n') p++; const char* enduri = p; if (*p == '>') p++; const char* title = NULL; char* endtitle; size_t titleidx = strcspn(p, "\"'("); if (p[titleidx] != '\0') { char delim = p[titleidx]; title = &p[titleidx+1]; switch (delim) { case '"': endtitle = strchr(title, '"'); break; case '\'': endtitle = strchr(title, '\''); break; case '(': endtitle = strchr(title, ')'); break; default: assert(!"Impossible case"); } if (endtitle == NULL) endtitle = &yytext[yyleng-1]; // sloppy parsing: be relaxed about termination } *yylval = scheme_make_list(s7_make_string_with_length(S7, ref, endref-ref), s7_make_string_with_length(S7, uri, enduri-uri), (title == NULL ? s7_f(S7) : s7_make_string_with_length(S7, title, endtitle-title)), NULL); return REFLINK; } /* an ordinary line, starting in column 1 */ {ORDINARY}.*"\n" { MAYBEBLANK; LVALFROM(yytext, yytext, yyleng); return TEXT; } /* The Gruber spec says that lines should be indented by at least * four spaces to be an indent, so this is neither one thing nor the * other. Take it to be an ordinary line, but should we warn about this? */ [ ]{1,3}{ORDINARY}.*"\n" { MAYBEBLANK; char* p = yytext; while (isspace(*p)) p++; LVALFROM(yytext, p, yyleng); return TEXT; } /* fallback: grab the rest of the line within the action * (we can't match ".*", since that's longer than ">" and so would match that above). * Note that we will match this if we encounter an input without a trailing line: * that isn't a problem, but it's unexpected, and may indicate a * missing case, so we probably want to shout here. */ . { StringBuilder buf = make_stringbuilder(); stringbuilder_append_c(buf, yytext[0]); int c; do { c = input(yyscanner); if (c == '\0') { // input returns 0 at end of input, not EOF // (the "" is useful for debugging, confusing otherwise?) stringbuilder_append_s(buf, ""); break; } else { stringbuilder_append_c(buf, c); } } while (c != '\n'); stringbuilder_terminate(buf); *yylval = s7_make_string(S7, buf->buf); // we might as well return this as TEXT const char* input_ident = (yyextra->string_buf ? yyextra->string_buf : (yyextra->filename == NULL ? "" : yyextra->filename)); fprintf(stderr, "Unexpected line %d of %s.\n[line is \"%s\"]\n", yyget_lineno(yyscanner), input_ident, buf->buf); stringbuilder_free(buf); return TEXT; } <> { // This is something of an edge-case, occurring when an input // file is missing a newline before EOF (the // parse_markdown_setup_string function below avoids this case).. // // yyless(0) doesn't work in this context (it appears), // so temporarily switch to scanning a buffer which has only a // blank link in it -- the code for '{HWS}*"\n"' (ie, blank // line in blockquote mode) will pop the right number of // BLOCKQUOTEEND lexemes. // // Compare the code below, in parse_markdown_setup_string, which // appears to partly duplicate the effect here, in the case where // we're parsing an input string. It might be that this can be // slimmed down, but it's not obvious, on brief experiment, that // the code here makes the code there fully redundant. // // I _think_ that using yy_scan_string here (as opposed to // yy_scan_buffer) means that flex will take care of the memory // for the copy. yy_switch_to_buffer(yy_scan_string("\n", yyscanner), yyscanner); } <> { BEGIN(INITIAL); return BLANK; } /* no special handling is required for EOF in the INITIAL case */ %% yyscan_t parse_markdown_setup_file(markdown_extra_t extra, const char* fn) { yyscan_t scanner; yylex_init_extra(extra, &scanner); extra->vspace_p = 0; extra->bq_level = 0; extra->found_annotation_p = 0; extra->string_buf = NULL; extra->filename = fn; extra->infile = NULL; if (fn != NULL) { FILE* infile = fopen(fn, "r"); if (infile == NULL) { // warning or error? #f or '()? scheme_eval("print-warning", s7_make_string(S7, "parse-markdown-file/metadata: can't open file ~a to read"), s7_make_string(S7, fn), 0); return NULL; // JUMP OUT } extra->infile = infile; yyset_in(infile, scanner); } if (markdowndebug) { yyset_debug(1, scanner); } return scanner; } yyscan_t parse_markdown_setup_string(markdown_extra_t extra, const char* s, size_t slen) { yyscan_t scanner; yylex_init_extra(extra, &scanner); extra->vspace_p = 0; extra->found_annotation_p = 0; extra->filename = NULL; extra->infile = NULL; // Set up the buffer for yy_scan_buffer. This involves // ensuring the string ends with a newline, and adding the // two zero bytes that yy_scan_buffer requires. We could use // yy_scan_string (which involves a further copy of the string) // but if we're adding the newline, we might as well do both jobs. // // We must add the newline, or else the markdown block parser // gets unhappy. I have tried adding this extra newline with a // yywrap() function which sets up a suitable buffer containing // only "\n", but that ends up becoming quite complicated, // for little real benefit (as well as apparently requiring me to // go a bit off-piste regarding the signature of yywrap, by using // yyguts* instead of yyscan_t). Since I do this copy here anyway // (at which point it's easy to add the newline), there's no // benefit to using yywrap. // // Since I added this stuff, I've reworked the way that // blockquotes are handled, so this _might_ not be completely // necessary. See above, at the pattern '<>'. char* t = malloc(slen+3); if (t == NULL) { fprintf(stderr, "Unable to allocate %ld bytes for input string!\n", slen+3); exit(1); } memcpy(t, s, slen); memcpy(&t[slen], "\n\0\0", 3); extra->string_buf = t; yy_scan_buffer(t, slen+3, scanner); yyset_lineno(1, scanner); return scanner; } void parse_markdown_finish(markdown_extra_t extra, yyscan_t scanner) { if (extra->string_buf) { free(extra->string_buf); extra->string_buf = NULL; } if (extra->infile) { fclose(extra->infile); extra->infile = NULL; } yylex_destroy(scanner); } /* The buffer bstart is of length blen, and ends with '\n'. * Create an s7 string from p, which points within the string, to the end, * omitting the trailing newline and other trailing whitespace. */ static s7_pointer string_from_buf(const char* bstart, const char* p, const size_t blen) { s7_pointer result; if (p < bstart || p > &bstart[blen]) { fprintf(stderr, "string_to_buf: pointer p not in correct range\n"); return s7_make_string(S7, ""); } const char* endp = bstart + blen - 1; while (isspace(*endp) && endp >= p) endp--; if (endp < p) { // unusual, but don't fail result = s7_make_string(S7, ""); } else { // endp now points at the last non-whitespace character size_t len = endp - p + 1; char* buf = alloca(len+1); memcpy(buf, p, len); buf[len] = '\0'; result = s7_make_string_with_length(S7, buf, len); } return result; } // Define this outside WITH_MAIN, so that it's available elsewhere for debugging // (eg, just after the call to YYLEX in foo.tab.c): // // yychar = YYLEX; // void display_one_lexeme(int, YYSTYPE, int); // display_one_lexeme(yychar, yylval, 1); void display_one_lexeme(int l, YYSTYPE v, int stderr_p) { FILE* f = (stderr_p ? stderr : stdout); switch (l) { case TEXT: s7w4("text: ", v, "\n", 1); break; case H1UNDERLINE: fprintf(f, "===\n"); break; case H2UNDERLINE: fprintf(f, "---\n"); break; case HR: fprintf(f, "horizontal rule\n"); break; case HN: s7w4("HN: ", v, "\n", 1); break; case ITEM: s7w4("item: ", v, "\n", 1); break; case INDENTED: s7w4("indented: ", v, "\n", 1); break; case B_INDENTED: s7w4("BLANK-indented: ", v, "\n", 1); break; case BLANK: fprintf(f, "BLANK\n"); break; case BLOCKQUOTESTART: fprintf(f, "
\n"); break; case BLOCKQUOTEEND: fprintf(f, "
\n"); break; case REFLINK: s7w4("reflink: ", v, "\n", 1); break; case ANNOTATION: s7w4("annotation:", v, "\n", 1); break; default: fprintf(f, "Unexpected lexeme: %d\n", l); } } #if WITH_MAIN #include #include #include "util.h" void s7w(const char* before, s7_pointer s, const char* after); YYSTYPE one_value; YYLTYPE locp; s7_scheme* S7; static void display_lexemes(yyscan_t scanner) { int l; while ((l = markdownlex(&one_value, &locp, scanner)) != 0) { display_one_lexeme(l, one_value, 0); } } static const char* progname; void Usage(void) { fprintf(stderr, "Usage: %s [foo.md]\n", progname); exit(1); } int main(int argc, char** argv) { const char* infilename = NULL; progname = argv[0]; switch (argc) { case 1: infilename = NULL; // redundant, with initialisation above break; case 2: if (argv[1][0] == '-') { Usage(); } else { infilename = argv[1]; } break; default: Usage(); } S7 = s7_init(); struct markdown_extra_s S; yyscan_t scanner = parse_markdown_setup_file(&S, infilename); display_lexemes(scanner); parse_markdown_finish(&S, scanner); } #endif