<?xml version="1.0" encoding="UTF-8"?>

<office:document xmlns:office="urn:oasis:names:tc:opendocument:xmlns:office:1.0"

xmlns:style="urn:oasis:names:tc:opendocument:xmlns:style:1.0"

xmlns:text="urn:oasis:names:tc:opendocument:xmlns:text:1.0"

xmlns:table="urn:oasis:names:tc:opendocument:xmlns:table:1.0"

xmlns:draw="urn:oasis:names:tc:opendocument:xmlns:drawing:1.0"

xmlns:fo="urn:oasis:names:tc:opendocument:xmlns:xsl-fo-compatible:1.0"

xmlns:xlink="http://www.w3.org/1999/xlink"

xmlns:dc="http://purl.org/dc/elements/1.1/"

xmlns:meta="urn:oasis:names:tc:opendocument:xmlns:meta:1.0"

xmlns:number="urn:oasis:names:tc:opendocument:xmlns:datastyle:1.0"

xmlns:svg="urn:oasis:names:tc:opendocument:xmlns:svg-compatible:1.0"

xmlns:chart="urn:oasis:names:tc:opendocument:xmlns:chart:1.0"

xmlns:dr3d="urn:oasis:names:tc:opendocument:xmlns:dr3d:1.0"

xmlns:math="http://www.w3.org/1998/Math/MathML"

xmlns:form="urn:oasis:names:tc:opendocument:xmlns:form:1.0"

xmlns:script="urn:oasis:names:tc:opendocument:xmlns:script:1.0"

xmlns:ooo="http://openoffice.org/2004/office"

xmlns:ooow="http://openoffice.org/2004/writer"

xmlns:oooc="http://openoffice.org/2004/calc"

xmlns:dom="http://www.w3.org/2001/xml-events"

xmlns:xforms="http://www.w3.org/2002/xforms"

xmlns:xsd="http://www.w3.org/2001/XMLSchema"

xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"

xmlns:rpt="http://openoffice.org/2005/report"

xmlns:of="urn:oasis:names:tc:opendocument:xmlns:of:1.2"

xmlns:xhtml="http://www.w3.org/1999/xhtml"

xmlns:grddl="http://www.w3.org/2003/g/data-view#"

xmlns:officeooo="http://openoffice.org/2009/office"

xmlns:tableooo="http://openoffice.org/2009/table"

xmlns:drawooo="http://openoffice.org/2010/draw"

xmlns:calcext="urn:org:documentfoundation:names:experimental:calc:xmlns:calcext:1.0"

xmlns:loext="urn:org:documentfoundation:names:experimental:office:xmlns:loext:1.0"

xmlns:field="urn:openoffice:names:experimental:ooo-ms-interop:xmlns:field:1.0"

xmlns:formx="urn:openoffice:names:experimental:ooxml-odf-interop:xmlns:form:1.0"

xmlns:css3t="http://www.w3.org/TR/css3-text/"

office:version="1.2"

office:mimetype="application/vnd.oasis.opendocument.text">

<office:font-face-decls>

<style:font-face style:name="Courier New" svg:font-family="'Courier New'"

style:font-adornments="Regular"

style:font-family-generic="modern"

style:font-pitch="fixed"/>

</office:font-face-decls>

<office:styles>

<style:style style:name="Standard" style:family="paragraph" style:class="text">

<style:paragraph-properties fo:margin-top="0in" fo:margin-bottom="0.15in" fo:text-align="justify" style:justify-single-word="false"/>

</style:style>

<style:style style:name="Preformatted_20_Text" style:display-name="Preformatted Text"

style:family="paragraph"

style:parent-style-name="Standard"

style:class="html">

<style:paragraph-properties fo:margin-top="0in" fo:margin-bottom="0in" fo:text-align="start"

style:justify-single-word="false"/>

<style:text-properties style:font-name="Courier New" fo:font-size="11pt"

style:font-name-asian="Courier New"

style:font-size-asian="11pt"

style:font-name-complex="Courier New"

style:font-size-complex="11pt"/>

</style:style>

<style:style style:name="Source_20_Text" style:display-name="Source Text"

style:family="text">

<style:text-properties style:font-name="Courier New" style:font-name-asian="Courier New"

style:font-name-complex="Courier New"

fo:font-size="11pt"/>

</style:style>

<style:style style:name="List" style:family="paragraph"

style:parent-style-name="Standard"

style:class="list">

<style:paragraph-properties fo:text-align="start" style:justify-single-word="false"/>

<style:text-properties style:font-size-asian="12pt"/>

</style:style>

<style:style style:name="Quotations" style:family="paragraph"

style:parent-style-name="Standard"

style:class="html">

<style:paragraph-properties fo:margin-left="0.3937in" fo:margin-right="0.3937in" fo:margin-top="0in"

fo:margin-bottom="0.1965in"

fo:text-align="justify" style:justify-single-word="false" fo:text-indent="0in"

style:auto-text-indent="false"/>

</style:style>

<style:style style:name="Table_20_Heading" style:display-name="Table Heading"

style:family="paragraph"

style:parent-style-name="Table_20_Contents"

style:class="extra">

<style:paragraph-properties fo:text-align="center" style:justify-single-word="false"

text:number-lines="false"

text:line-number="0"/>

<style:text-properties fo:font-weight="bold" style:font-weight-asian="bold"

style:font-weight-complex="bold"/>

</style:style>

<style:style style:name="Horizontal_20_Line" style:display-name="Horizontal Line"

style:family="paragraph"

style:parent-style-name="Standard"

style:class="html">

<style:paragraph-properties fo:margin-top="0in" fo:margin-bottom="0.1965in"

style:border-line-width-bottom="0.0008in 0.0138in 0.0008in"

fo:padding="0in"

fo:border-left="none"

fo:border-right="none"

fo:border-top="none"

fo:border-bottom="0.0154in double #808080"

text:number-lines="false"

text:line-number="0"

style:join-border="false"/>

<style:text-properties fo:font-size="6pt" style:font-size-asian="6pt" style:font-size-complex="6pt"/>

</style:style>

<style:style style:name="Footnote_20_anchor" style:display-name="Footnote anchor" style:family="text"> <style:text-properties style:text-position="super 58%"/> </style:style>

<style:style style:name="TOC_Item" style:family="paragraph" style:parent-style-name="Standard">

<style:paragraph-properties>

<style:tab-stops>

<style:tab-stop style:position="6.7283in" style:type="right" style:leader-style="dotted" style:leader-text="."/>

</style:tab-stops>

</style:paragraph-properties>

</style:style>

<text:notes-configuration text:note-class="footnote" text:default-style-name="Footnote" text:citation-style-name="Footnote_20_Symbol" text:citation-body-style-name="Footnote_20_anchor" text:master-page-name="Footnote" style:num-format="a" text:start-value="0" text:footnotes-position="page" text:start-numbering-at="page"/>

<text:notes-configuration text:note-class="endnote" text:default-style-name="Endnote" text:citation-style-name="Endnote_20_Symbol" text:citation-body-style-name="Endnote_20_anchor" text:master-page-name="Endnote" style:num-format="1" text:start-value="0"/>

</office:styles>

<office:automatic-styles> <style:style style:name="MMD-Italic" style:family="text">

<style:text-properties fo:font-style="italic" style:font-style-asian="italic"

style:font-style-complex="italic"/>

</style:style>

<style:style style:name="MMD-Bold" style:family="text">

<style:text-properties fo:font-weight="bold" style:font-weight-asian="bold"

style:font-weight-complex="bold"/>

</style:style>

<style:style style:name="MMD-Superscript" style:family="text">

<style:text-properties style:text-position="super 58%"/>

</style:style>

<style:style style:name="MMD-Subscript" style:family="text">

<style:text-properties style:text-position="sub 58%"/>

</style:style>

<style:style style:name="Strike" style:family="text">

<style:text-properties style:text-line-through-style="solid" />

</style:style>

<style:style style:name="Underline" style:family="text">

<style:text-properties style:text-underline-style="solid" style:text-underline-color="font-color"/>

</style:style>

<style:style style:name="Highlight" style:family="text">

<style:text-properties fo:background-color="#FFFF00" />

</style:style>

<style:style style:name="Comment" style:family="text">

<style:text-properties fo:color="#0000BB" />

</style:style>

<style:style style:name="MMD-Table" style:family="paragraph" style:parent-style-name="Standard">

<style:paragraph-properties fo:margin-top="0in" fo:margin-bottom="0.05in"/>

</style:style>

<style:style style:name="MMD-Table-Center" style:family="paragraph" style:parent-style-name="MMD-Table">

<style:paragraph-properties fo:text-align="center" style:justify-single-word="false"/>

</style:style>

<style:style style:name="MMD-Table-Right" style:family="paragraph" style:parent-style-name="MMD-Table">

<style:paragraph-properties fo:text-align="right" style:justify-single-word="false"/>

</style:style>

<style:style style:name="P2" style:family="paragraph" style:parent-style-name="Standard"

style:list-style-name="L2">

<style:paragraph-properties fo:text-align="start" style:justify-single-word="false"/>

</style:style>

<style:style style:name="fr1" style:family="graphic" style:parent-style-name="Frame">

<style:graphic-properties style:print-content="true" style:vertical-pos="top"

style:vertical-rel="baseline"

fo:padding="0in"

fo:border="none"

style:shadow="none"/>

</style:style>

<style:style style:name="P1" style:family="paragraph" style:parent-style-name="Standard"

style:list-style-name="L1"/>

<text:list-style style:name="L1">

<text:list-level-style-bullet text:level="1" text:style-name="Numbering_20_Symbols" style:num-suffix="." text:bullet-char="•">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="0.5in" fo:text-indent="-0.25in" fo:margin-left="0.5in"/>

</style:list-level-properties>

</text:list-level-style-bullet>

<text:list-level-style-bullet text:level="2" text:style-name="Numbering_20_Symbols" style:num-suffix="." text:bullet-char="◦">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="0.75in" fo:text-indent="-0.25in" fo:margin-left="0.75in"/>

</style:list-level-properties>

</text:list-level-style-bullet>

<text:list-level-style-bullet text:level="3" text:style-name="Numbering_20_Symbols" style:num-suffix="." text:bullet-char="▪">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="1in" fo:text-indent="-0.25in" fo:margin-left="1in"/>

</style:list-level-properties>

</text:list-level-style-bullet>

<text:list-level-style-number text:level="4" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="1.25in" fo:text-indent="-0.25in" fo:margin-left="1.25in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="5" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="1.5in" fo:text-indent="-0.25in" fo:margin-left="1.5in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="6" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="1.75in" fo:text-indent="-0.25in" fo:margin-left="1.75in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="7" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="2in" fo:text-indent="-0.25in" fo:margin-left="2in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="8" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="2.25in" fo:text-indent="-0.25in" fo:margin-left="2.25in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="9" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="2.5in" fo:text-indent="-0.25in" fo:margin-left="2.5in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="10" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="2.75in" fo:text-indent="-0.25in" fo:margin-left="2.75in"/>

</style:list-level-properties>

</text:list-level-style-number>

</text:list-style>

<text:list-style style:name="L2">

<text:list-level-style-number text:level="1" text:style-name="Standard" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="0.5in" fo:text-indent="-0.25in" fo:margin-left="0.5in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="2" text:style-name="Standard" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="0.75in" fo:text-indent="-0.25in" fo:margin-left="0.75in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="3" text:style-name="Standard" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="1in" fo:text-indent="-0.25in" fo:margin-left="1in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="4" text:style-name="Standard" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="1.25in" fo:text-indent="-0.25in" fo:margin-left="1.25in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="5" text:style-name="Standard" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="1.5in" fo:text-indent="-0.25in" fo:margin-left="1.5in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="6" text:style-name="Standard" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="1.75in" fo:text-indent="-0.25in" fo:margin-left="1.75in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="7" text:style-name="Standard" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="2in" fo:text-indent="-0.25in" fo:margin-left="2in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="8" text:style-name="Standard" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="2.25in" fo:text-indent="-0.25in" fo:margin-left="2.25in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="9" text:style-name="Standard" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="2.5in" fo:text-indent="-0.25in" fo:margin-left="2.5in"/>

</style:list-level-properties>

</text:list-level-style-number>

<text:list-level-style-number text:level="10" text:style-name="Standard" style:num-suffix="." style:num-format="1">

<style:list-level-properties text:list-level-position-and-space-mode="label-alignment">

<style:list-level-label-alignment text:label-followed-by="listtab" text:list-tab-stop-position="2.75in" fo:text-indent="-0.25in" fo:margin-left="2.75in"/>

</style:list-level-properties>

</text:list-level-style-number>

</text:list-style>

</office:automatic-styles>

<office:master-styles>

<style:master-page style:name="Endnote" >

<style:header><text:h text:outline-level="2">Bibliography</text:h></style:header></style:master-page>

<style:master-page style:name="Footnote" style:page-layout-name="pm2"/>

</office:master-styles>

<office:meta>

<dc:title>MultiMarkdown v6 Development Notes</dc:title>

<dc:creator>Fletcher T. Penney</dc:creator>

<meta:user-defined meta:name="date">2023-06-10</meta:user-defined>

<meta:user-defined meta:name="uuid">dd2d8e76-dc2d-416d-9acd-5395d20871c2</meta:user-defined>

</office:meta>

<office:body>

<office:text>

<text:h text:outline-level="3"><text:bookmark text:name="introduction"/>Introduction</text:h>

<text:p text:style-name="Standard">This document includes some notes on the development of MultiMarkdown (MMD) v6. Most of it

will be interesting only to other developers or those needing to choose the

absolute &#8220;best&#8221; Markdown (MD) implementation for their needs &#8211; it is not required

reading to understand how the software works.</text:p>

<text:h text:outline-level="4"><text:bookmark text:name="whyanewversion"/>Why a New Version?</text:h>

<text:p text:style-name="Standard">MultiMarkdown version 5 was released in November of 2015, but the codebase was

essentially the same as that of v4 &#8211; and that was released in beta in April

of 2013. A few key things prompted work on a new version:</text:p>

<text:list text:style-name="L1">

<text:list-item>

<text:p text:style-name="Standard">Accuracy &#8211; MMD v4 and v5 were the most accurate versions yet, and a lot of

effort went into finding and resolving various edge cases. However, it began

to feel like a game of whack-a-mole where new bugs would creep in every time I

fixed an old one. The PEG<text:note text:id="gn1" text:note-class="glossary"><text:note-body><text:p text:style-name="Footnote">Parsing Expression Grammar <text:a xlink:type="simple" xlink:href="https://en.wikipedia.org/wiki/Parsing_expression_grammar">https://en.wikipedia.org/wiki/Parsing_expression_grammar</text:a></text:p></text:note-body></text:note> began to feel rather convoluted in spots, even

though it did allow for a precise (if not always accurate) specification of

the grammar.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">Performance &#8211; &#8220;Back in the day&#8221; <text:a xlink:type="simple" xlink:href="https://github.com/jgm/peg-markdown">peg-markdown</text:a> was one of the fastest

Markdown parsers around. MMD v3 was based on peg-markdown, and would leap-

frog with it in terms of performance. Then <text:a xlink:type="simple" xlink:href="http://commonmark.org/">CommonMark</text:a> was released, which

was a bit faster. Then a couple of years went by and CommonMark became <text:span text:style-name="MMD-Italic">much</text:span>

faster &#8211; in one of my test suites, MMD v 5.4.0 takes about 25 times longer to

process a long document than CommonMark 0.27.0.</text:p></text:list-item>

</text:list>

<text:p text:style-name="Standard">In the spring of 2016, I decided I wanted to rewrite MultiMarkdown from scratch,

building the parser myself rather than relying on a pre-rolled solution. (I

had been using <text:a xlink:type="simple" xlink:href="https://github.com/ooc-lang/greg">greg</text:a> to compile the PEG

into parser code. It worked well overall, but lacked some features I needed,

requiring a lot of workarounds.)</text:p>

<text:h text:outline-level="3"><text:bookmark text:name="firstattempt"/>First Attempt</text:h>

<text:p text:style-name="Standard">My first attempt started by hand-crafting a parser that scanned through the

document a line at a time, deciding what to do with each line as it found

them. I used regex parsers made with <text:a xlink:type="simple" xlink:href="http://re2c.org/index.html">re2c</text:a> to

help classify each line, and then a separate parser layer to process groups of

lines into blocks. Initially this approach worked well, and was really

efficient. But I quickly began to code my way into a dead-end &#8211; the strategy

was not elegant enough to handle things like nested lists, etc.</text:p>

<text:p text:style-name="Standard">One thing that did turn out well from the first attempt, however, was an

approach for handling <text:span text:style-name="Source_20_Text">&lt;emph&gt;</text:span> and <text:span text:style-name="Source_20_Text">&lt;strong&gt;</text:span> parsing. I&#8217;ve learned over the

years that this can be one of the hardest parts of coding accurately for

Markdown. There are many examples that are obvious to a person, but difficult

to properly &#8220;explain&#8221; how to parse to a computer.</text:p>

<text:p text:style-name="Standard">No solution is perfect, but I developed an approach that seems to accurately

handle a wide range of situations without a great deal of complexity:</text:p>

<text:list text:style-name="L2">

<text:list-item>

<text:p text:style-name="Standard">Scan the documents for asterisks (<text:span text:style-name="Source_20_Text">*</text:span>). Each one will be handled one at a

time.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">Unlike brackets (<text:span text:style-name="Source_20_Text">[</text:span> and <text:span text:style-name="Source_20_Text">]</text:span>), an asterisk is &#8220;ambidextrous&#8221;, in that it

may be able to open a matched pair of asterisks, close a pair, or both. For

example, in <text:span text:style-name="Source_20_Text">foo *bar* foo</text:span>:</text:p>

<text:list text:style-name="L2">

<text:list-item>

<text:p text:style-name="Standard">The first asterisk can open a pair, but not close one.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">The second asterisk can close a pair, but not open one.</text:p></text:list-item>

</text:list></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">So, once the asterisks have been identified, each has to be examined to

determine whether it can open/close/both. The algorithm is not that complex,

but I&#8217;ll describe it in general terms. Check the code for more specifics.

This approach seems to work, but might still need some slight tweaking. In

the future, I&#8217;ll codify this better in language rather than just in code.</text:p>

<text:list text:style-name="L2">

<text:list-item>

<text:p text:style-name="Standard">If there is whitespace to the left of an asterisk, it can&#8217;t close.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">If there is whitespace or punctuation to the right it can&#8217;t open.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">&#8220;Runs&#8221; of asterisks, e.g. <text:span text:style-name="Source_20_Text">**bar</text:span> are treated as a unit in terms of

looking left/right.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">Asterisks inside a word are a bit trickier &#8211; we look at the number of

asterisks before the word, the number in the current run, and the number

of asterisks after the word to determine which combinations, if any, are

permitted.</text:p></text:list-item>

</text:list></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">Once all asterisks have been tagged as able to open/close/both, we proceed

through them in order:</text:p>

<text:list text:style-name="L2">

<text:list-item>

<text:p text:style-name="Standard">When we encounter a tag that can close, we look to see if there is a

previous opener that has not been paired off. If so, pair the two and

remove the opener from the list of available asterisks.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">When we encounter an opener, add it to the stack of available openers.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">When encounter an asterisk that can do both, see if it can close an

existing opener. If not, then add it to the stack.</text:p></text:list-item>

</text:list></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">After all tokens in the block have been paired, then we look for nesting

pairs of asterisks in order to create <text:span text:style-name="Source_20_Text">&lt;emph&gt;</text:span> and <text:span text:style-name="Source_20_Text">&lt;strong&gt;</text:span> sets. For

example, assume we have six asterisks wrapped around a word, three in front,

and three after. The asterisks are indicated with numbers: <text:span text:style-name="Source_20_Text">123foo456</text:span>. We

proceed in the following manner:</text:p>

<text:list text:style-name="L2">

<text:list-item>

<text:p text:style-name="Standard">Based on the pairing algorithm above, these asterisks would be paired as

follows, with matching asterisks sharing numbers &#8211; <text:span text:style-name="Source_20_Text">123foo321</text:span>.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">Moving forwards, we come to asterisk &#8220;1&#8221;. It is followed by an

asterisk, so we check to see if they should be grouped as a <text:span text:style-name="Source_20_Text">&lt;strong&gt;</text:span>.

Since the &#8220;1&#8221; asterisks are wrapped immediately outside the &#8220;2&#8221; asterisks,

they are joined together. More than two pairs can&#8217;t be joined, so we now

get the following &#8211; <text:span text:style-name="Source_20_Text">112foo211</text:span>, where the &#8220;11&#8221; represents the opening

and closing of a <text:span text:style-name="Source_20_Text">&lt;strong&gt;</text:span>, and the &#8220;2&#8221; represents a <text:span text:style-name="Source_20_Text">&lt;emph&gt;</text:span>.</text:p></text:list-item>

</text:list></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">When matching a pair, any unclosed openers that are on the stack are

removed, preventing pairs from &#8220;crossing&#8221; or &#8220;intersecting&#8221;. Pairs can wrap

around each other, e.g. <text:span text:style-name="Source_20_Text">[(foo)]</text:span>, but not intersect like <text:span text:style-name="Source_20_Text">[(foo])</text:span>. In the

second case, the brackets would close, removing the <text:span text:style-name="Source_20_Text">(</text:span> from the stack.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">This same approach is used in all tokens that are matched in pairs&#8211;

<text:span text:style-name="Source_20_Text">[foo]</text:span>, <text:span text:style-name="Source_20_Text">(foo)</text:span>, <text:span text:style-name="Source_20_Text">_foo_</text:span>, etc. There&#8217;s slightly more to it, but once you

figure out how to assign opening/closing ability, the rest is easy. By using

a stack to track available openers, it can be performed efficiently.</text:p></text:list-item>

</text:list>

<text:p text:style-name="Standard">In my testing, this approach has worked quite well. It handles all the basic

scenarios I&#8217;ve thrown at it, and all of the &#8220;basic&#8221; and &#8220;devious&#8221; edge cases I

have thought of (some of these don&#8217;t necessarily have a &#8220;right&#8221; answer &#8211; but

v6 gives consistency answers that seem as reasonable as any others to me).

There are also three more edge cases I&#8217;ve come up can still stump it, and

ironically they are handled correctly by most implementations. They just

don&#8217;t follow the rules above. I&#8217;ll continue to work on this.</text:p>

<text:p text:style-name="Standard">In the end, I scrapped this effort, but kept the lessons learned in the token

pairing algorithm.</text:p>

<text:h text:outline-level="3"><text:bookmark text:name="secondattempt"/>Second Attempt</text:h>

<text:p text:style-name="Standard">I tried again this past Fall. This time, I approached the problem with lots

of reading. <text:span text:style-name="MMD-Italic">Lots and lots</text:span> of reading &#8211; tons of websites, computer science

journal articles, PhD theses, etc. Learned a lot about lexers, and a lot

about parsers, including hand-crafting vs using parser generators. In brief:</text:p>

<text:list text:style-name="L2">

<text:list-item>

<text:p text:style-name="Standard">I learned about the <text:a xlink:type="simple" xlink:href="https://en.wikipedia.org/wiki/Aho-Corasick_algorithm">Aho–Corasick algorithm</text:a>, which is a great way to

efficiently search a string for multiple target strings at once. I used this

to create a custom lexer to identify tokens in a MultiMarkdown text document

(e.g. <text:span text:style-name="Source_20_Text">*</text:span>, <text:span text:style-name="Source_20_Text">[</text:span>, <text:span text:style-name="Source_20_Text">{++</text:span>, etc.). I learned a lot, and had a good time working

out the implementation. This code efficiently allowed me to break a string of

text into the tokens that mattered for Markdown parsing.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">However, in a few instances I really needed some features of regular

expressions to simplify more complex structures. After a quick bit of testing,

using re2c to create a tokenizer was just as efficient, and allowed me to

incorporate some regex functionality that simplified later parsing. I&#8217;ll keep

the Aho-Corasick stuff around, and will probably experiment more with it

later. But I didn&#8217;t need it for MMD now. <text:span text:style-name="Source_20_Text">lexer.re</text:span> contains the source for

the tokenizer.</text:p></text:list-item>

</text:list>

<text:p text:style-name="Standard">I looked long and hard for a way to simplify the parsing algorithm to try and

&#8220;touch&#8221; each token only once. Ideally, the program could step through each

token, and decide when to create a new block, when to pair things together,

etc. But I&#8217;m not convinced it&#8217;s possible. Since Markdown&#8217;s grammar varies

based on context, it seems to work best when handled in distinct phases:</text:p>

<text:list text:style-name="L2">

<text:list-item>

<text:p text:style-name="Standard">Tokenize the string to identify key sections of text. This includes line

breaks, allowing the text to be examined one line at time.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">Join series of lines together into blocks, such as paragraphs, code blocks,

lists, etc.</text:p></text:list-item>

<text:list-item>

<text:p text:style-name="Standard">The tokens inside each block can then be paired together to create more

complex syntax such as links, strong, emphasis, etc.</text:p></text:list-item>

</text:list>

<text:p text:style-name="Standard">To handle the block parsing, I started off using the Aho-Corasick code to

handle my first attempt. I had actually implemented some basic regex

functionality, and used that to group lines together to create blocks. But

this quickly fell apart in the face of more complex structures such as

recursive lists. After a lot of searching, and <text:span text:style-name="MMD-Italic">tons</text:span> more reading, I

ultimately decided to use a parser generator to handle the task of group lines

into blocks. <text:span text:style-name="Source_20_Text">parser.y</text:span> has the source for this, and it is processed by the

<text:a xlink:type="simple" xlink:href="http://www.hwaci.com/sw/lemon/">lemon</text:a> parser generator to create the actual code.</text:p>

<text:p text:style-name="Standard">I chose to do this because hand-crafting the block parser would be complex.

The end result would likely be difficult to read and understand, which would

make it difficult to update later on. Using the parser generator allows me to

write things out in a way that can more easily be understood by a person. In

all likelihood, the performance is probably as good as anything I could do

anyway, if not better.</text:p>

<text:p text:style-name="Standard">Because lemon is a LALR(1) parser, it does require a bit of thinking ahead

about how to create the grammar used. But so far, it has been able to handle

everything I have thrown at it.</text:p>

<text:h text:outline-level="3"><text:bookmark text:name="optimization"/>Optimization</text:h>

<text:p text:style-name="Standard">One of my goals for MMD 6 was performance. So I&#8217;ve paid attention to speed

along the way, and have tried to use a few tricks to keep things fast. Here

are some things I&#8217;ve learned along the way. In no particular order:</text:p>

<text:h text:outline-level="4"><text:bookmark text:name="memoryallocation"/>Memory Allocation</text:h>

<text:p text:style-name="Standard">When parsing a long document, a <text:span text:style-name="MMD-Italic">lot</text:span> of token structures are created. Each

one requires a small bit of memory to be allocated. In aggregate, that time

added up and slowed down performance.</text:p>

<text:p text:style-name="Standard">After reading for a bit, I ended up coming up with an approach that uses

larger chunks of memory. I allocate pools of of memory in large slabs for

smaller &quot;objects. For example, I allocate memory for 1024 tokens at a

single time, and then dole that memory out as needed. When the slab is empty,

a new one is allocated. This dramatically improved performance.</text:p>

<text:p text:style-name="Standard">When pairing tokens, I created a new stack for each block. I realized that an

empty stack didn&#8217;t have any &#8220;leftover&#8221; cruft to interfere with re-use, so I

just used one for the entire document. Again a sizeable improvement in

performance from only allocating one object instead of many. When recursing

to a deeper level, the stack just gets deeper, but earlier levels aren&#8217;t

modified.</text:p>

<text:p text:style-name="Standard">Speaking of tokens, I realized that the average document contains a lot of

single spaces (there&#8217;s one between every two words I have written, for

example.) The vast majority of the time, these single spaces have no effect

on the output of Markdown documents. I changed my whitespace token search to

only flag runs of 2 or more spaces, dramatically reducing the number of

tokens. This gives the benefit of needing fewer memory allocations, and also

reduces the number of tokens that need to be processed later on. The only

downside is remember to check for a single space character in a few instances

where it matters.</text:p>

<text:h text:outline-level="4"><text:bookmark text:name="properinputbuffering"/>Proper input buffering</text:h>

<text:p text:style-name="Standard">When I first began last spring, I was amazed to see how much time was being

spent by MultiMarkdown simply reading the input file. Then I discovered it

was because I was reading it one character at a time. I switched to using a

buffered read approach and the time to read the file went to almost nothing. I

experimented with different buffer sizes, but they did not seem to make a

measurable difference.</text:p>

<text:h text:outline-level="4"><text:bookmark text:name="outputbuffering"/>Output Buffering</text:h>

<text:p text:style-name="Standard">I experimented with different approaches to creating the output after parsing.

I tried printing directly to <text:span text:style-name="Source_20_Text">stdout</text:span>, and even played with different

buffering settings. None of those seemed to work well, and all were slower

than using the <text:span text:style-name="Source_20_Text">d_string</text:span> approach (formerly called <text:span text:style-name="Source_20_Text">GString</text:span> in MMD 5).</text:p>

<text:h text:outline-level="4"><text:bookmark text:name="fastsearches"/>Fast Searches</text:h>

<text:p text:style-name="Standard">After getting basic Markdown functionality complete, I discovered during

testing that the time required to parse a document grew exponentially as the

document grew longer. Performance was on par with CommonMark for shorter

documents, but fell increasingly behind in larger tests. Time profiling found

that the culprit was searching for link definitions when they didn&#8217;t exist.

My first approach was to keep a stack of used link definitions, and to iterate

through them when necessary. In long documents, this performs very poorly.

More research and I ended up using

<text:a xlink:type="simple" xlink:href="http://troydhanson.github.io/uthash/">uthash</text:a>. This allows me to search for

a link (or footnote, etc.) by &#8220;name&#8221; rather than searching through an array.

This allowed me to get MMD&#8217;s performance back to O(n), taking roughly twice as

much time to process a document that is twice as long.</text:p>

<text:h text:outline-level="4"><text:bookmark text:name="efficientutilityfunctions"/>Efficient Utility Functions</text:h>

<text:p text:style-name="Standard">It is frequently necessary when parsing Markdown to check what sort of

character we are dealing with at a certain position &#8211; a letter, whitespace,

punctuation, etc. I created a lookup table for this via <text:span text:style-name="Source_20_Text">char_lookup.c</text:span> and

hard-coded it in <text:span text:style-name="Source_20_Text">char.c</text:span>. These routines allow me to quickly, and

consistently, classify any byte within a document. This saved a lot of

programming time, and saved time tracking down bugs from handling things

slightly differently under different circumstances. I also suspect it

improved performance, but don&#8217;t have the data to back it up.</text:p>

<text:h text:outline-level="4"><text:bookmark text:name="testingwhilewriting"/>Testing While Writing</text:h>

<text:p text:style-name="Standard">I developed several chunks of code in parallel while creating MMD 6. The vast

majority of it was developed largely in a <text:a xlink:type="simple" xlink:href="https://en.wikipedia.org/wiki/Test-driven_development">test-driven development</text:a> approach.

The other code was largely created with extensive unit testing to accomplish

this.</text:p>

<text:p text:style-name="Standard">MMD isn&#8217;t particularly amenable to this approach at the small level, but

instead I relied more on integration testing with an ever-growing collection

of text files and the corresponding HTML files in the MMD 6 test suite. This

allowed me to ensure new features work properly and that old features aren&#8217;t

broken. At this time, there are 29 text files in the test suite, and many

more to come.</text:p>

<text:h text:outline-level="4"><text:bookmark text:name="otherlessons"/>Other Lessons</text:h>

<text:p text:style-name="Standard">Some things that didn&#8217;t do me any good&#8230;.</text:p>

<text:p text:style-name="Standard">I considered differences between using <text:span text:style-name="Source_20_Text">malloc</text:span> and <text:span text:style-name="Source_20_Text">calloc</text:span> when initializing

tokens. The time saved by using <text:span text:style-name="Source_20_Text">malloc</text:span> was basically exactly offset by the

initial time required to initialize the token to default null values as

compared to using <text:span text:style-name="Source_20_Text">calloc</text:span>. When trying <text:span text:style-name="Source_20_Text">calloc</text:span> failed to help me out

(thinking that clearing a single slab in the object pool would be faster), I

stuck with <text:span text:style-name="Source_20_Text">malloc</text:span> as it makes more sense to me in my workflow.</text:p>

<text:p text:style-name="Standard">I read a bit about <text:a xlink:type="simple" xlink:href="http://www.catb.org/esr/structure-packing/">struct padding</text:a> and reordered some of my structs. It was

until later that I discovered the <text:span text:style-name="Source_20_Text">-Wpadded</text:span> option, and it&#8217;s not clear

whether my changes modified anything. Since the structs were being padded

automatically, there was no noticeable performance change, and I didn&#8217;t have

the tools to measure whether I could have improved memory usage at all. Not

sure this would be worth the effort &#8211; much lower hanging fruit available.</text:p>

<text:h text:outline-level="3"><text:bookmark text:name="performance"/>Performance</text:h>

<text:p text:style-name="Standard">Basic tests show that currently MMD 6 takes about 20&#8211;25% longer the CommonMark