💾 Archived View for gmi.karl.berlin › smu.html captured on 2023-05-24 at 17:43:58.
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Hacking on "smu", a Minimal Markdown Parser</title>
<link href="https://www.karl.berlin/atom.xml" type="application/atom+xml" rel="alternate" title="Atom feed for blog posts" />
<style>
body {
font-family: sans-serif;
margin: 0 auto;
max-width: 48rem;
line-height: 1.45;
padding: 0.5rem 0 1.6rem;
box-shadow: 0 0 2rem 0 #bbb;
border-radius: 0 0 0.6rem 0.6rem;
}
main {
padding: 0 1.4rem;
hyphens: auto;
}
code {
background: #eee;
padding: 0.3rem;
tab-size: 4;
}
pre code {
display: block;
overflow-x: auto;
padding: 0.3rem 0.6rem;
}
nav ul {
margin: 0;
padding: 0;
display: flex;
background: #17a;
}
nav li {
list-style: none;
}
nav li * {
display: block;
padding: 0.4rem 0.4rem;
color: white;
}
nav li strong {
padding-left: 1.5rem;
padding-right: 1rem;
}
nav a {
text-decoration: none;
}
nav a:hover {
background: #069;
}
</style>
</head>
<nav>
<ul>
<li><strong>Karl Bartel</strong></li>
<li><a href="index.html">Home</a></li>
<li><a href="projects.html">Projects</a></li>
</ul>
</nav>
<main>
<h1>Hacking on "smu", a Minimal Markdown Parser</h1>
<h2>Introduction</h2>
<p>I wanted to get my hands dirty and improve a <a href="https://suckless.org/">suckless</a> related program. So I had a look at the <a href="https://suckless.org/project_ideas/">project ideas page</a> and picked out something simple:</p>
<blockquote><p>Improve the Markdown parser used by the suckless wiki called "smu" to conform more to Markdown. for example for nested codeblocks. Difficulty: trivial-medium.<br />
Specs: http://daringfireball.net/projects/markdown/syntax.text and http://commonmark.org/.<br />
smu: https://github.com/Gottox/smu </p>
</blockquote>
<h2>First Impressions</h2>
<p>While C is pleasantly simple in many regards, writing good code can be quite cumbersome if you're not used to it. I didn't write any serious amount of C for many years and I tend to think that C is generally a bad choice for anything that does large amounts of string manipulation. I was expecting many regular expressions and some hard-to-get-right memory allocation code. To my surprise, I didn't find a single regex and hardly any memory management code. Instead of regexes, the code relied on basic string functions like <code>strstr</code> and lots of manually-iterating-through-char-arrays.</p>
<p>Like most suckless programs, smu consists of a single C file with only a few hundred lines (624 in this case), had no dependencies and compiled instantly without the need to run a <code>configure</code> script.</p>
<h2>How smu Manages to Stay Simple</h2>
<h3>Put Logic Into Data instead of Code</h3>
<p>Markdown has a large amount of different syntax elements, but many of them behave in similar ways. Smu takes advantage of this by declaring the different syntax elements in data structures that can be processed by a small amount of different functions. Here's one example:</p>
<pre><code class="language-c">static Tag lineprefix[] = {
{ " ", 0, "<pre><code>", "</code></pre>" },
{ "\t", 0, "<pre><code>", "</code></pre>" },
{ "> ", 2, "<blockquote>", "</blockquote>" },
{ "###### ", 1, "<h6>", "</h6>" },
{ "##### ", 1, "<h5>", "</h5>" },
{ "#### ", 1, "<h4>", "</h4>" },
{ "### ", 1, "<h3>", "</h3>" },
{ "## ", 1, "<h2>", "</h2>" },
{ "# ", 1, "<h1>", "</h1>" },
{ "- - -\n", 1, "<hr />", ""},
};
</code></pre>
<p>These declarations provide the basis of handling code indents (both with spaces and with tabs), blockquotes, headings of different levels and horizontal rules. All of these different syntax elements can now be processed by a single small functions (~45 lines). Not only does this reduce the amount of code, but it also makes it a lot easier to get an overview of the possible markup constructs and how they relate to each other.</p>
<h3>Avoid Memory Management</h3>
<p>Since these syntax elements have to be parsed into different parts (markdown syntax, content, link title, link target, etc.), I was expecting many strings allocations to hold these parts. But smu gets around this in most cases by doing one of these two things:</p>
<ul>
<li>Instead of saving the parsed data structures, the corresponding output is generated immediately, so that the parsed strings don't have to be saved at all</li>
<li>Instead of allocation a new string, two pointers are used to mark the desired substring in smu's input.</li>
</ul>
<h3>Simplify Spec</h3>
<p>Markdown is not something that falls out of a beautiful mathematical model, rather it is grown over the time, driven by what people "mean" when they write pseudo-plaintext. This led to a bunch of weird edge case handling rules and syntax oddities. Smu took the liberty to ignore parts of markdown (reference style links) and handle some details differently (escaping, white space handling).</p>
<h2>Changing smu</h2>
<h3>Test Suite</h3>
<p>As mentioned above, I didn't write C for a long time. I also was not sure how all Markdown should be interpreted in detail. So to prevent me from breaking everything, I needed some way to spot regressions or other bugs. When looking for Markdown test cases, I found <a href="https://github.com/michelf/mdtest/">mdtest</a> and took a set of basis tests from it that mostly worked with smu. Then I looked through the remaining differences and tried to understand why smu delivered different results. That way, the tests did not only provide some safety while hacking on smu, but also showed me where it differed from other markdown implementations.</p>
<p>To turn the <em>(input, expected output)</em> pairs into automated test cases, I committed both to git and added a make target that regenerates the output and runs <code>git diff</code> on the test directory. When the diff shows no output, the tests have passed! This will give more false positives than mdtest's algorithm that accounts for insignificant white space, but it is much simpler.</p>
<h3>CommonMark Compatibility</h3>
<p>These differences provided a nice starting ground for the first steps towards improved markdown compatibility. I could pick some minor differences that could easily be adjusted by modifying just a few line of code. At the same time, I collected a list of differences to CommonMark that I noticed but couldn't (or didn't want to) fix right away in order to add that to the documentation.</p>
<p>By doing a few of these changes I got more confident when changing the code and felt ready to start bigger changes. For my personal usage, one feature omitted by smu proved to be a annoyance: code fences. Without code fences, copy/pasting code to and from your markdown code blocks requires changes in indentation, which is error prone and a bit of a hassle. To implement code fences, extending one of the lists of syntax elements was not enough, since they work neither by prefixing every line of the block nor are the surrounding markers for other elements sufficient to accurately capture their block behavior. So I unfortunately had to add another parsing function to handle them correctly. That however, worked without much surprises and yielded results to my satisfaction.</p>
<p>One other conceptual difference I introduced was a different escaping rules. Originally, smu had the simple rule of escaping the characters <code>\ ` * _ { } [ ] ( ) # + - . !</code>. This worked fine in most cases, but brought downsides with it:</p>
<ol>
<li>There is not way to escape text parts that look like HTML but aren't</li>
<li>Some code parts containing backslashes lost their backslashes unless you escape them (bad for copy/paste).</li>
</ol>
<p>To remedy the first problem, I looked up the <a href="https://spec.commonmark.org/0.29/#backslash-escapes">CommonMark escaping rules</a> and added all characters from the CommomMark list to smu's list of escaped characters. Inside code spans, <code>\`</code> was the only escape needed to be allowed, since it would mean the end of a code span without escape and all other characters have no special meaning inside code spans/blocks. But this was an ugly special case in the code and would also lead to silently broken code samples when you add code that does contain a literal <code>\`</code>. How does CommonMark deal with this? The rules for code spans and code blocks allow an unlimited amount of different start and end markers, so markers can be chosen that are not present in the code itself. I chose a subset of these rules that could be expressed with smu's existing matching declarations, so that you can write <code>`` ` ``</code> if you want a code span that contains a single backtick (The pair of single white spaces is ignored). When first reading the CommonMark specs, I felt that these rules were strange and arbitrary, but after trying to find simpler alternative, I started to appreciate the spec more and more, even though I still consider parts of it to allow an unnecessarily amount of different syntaxes.</p>
<!--
### Different approaches