Merge: nitunit: Use markdown2

[nit.git] / lib / markdown2 / markdown_inline_parsing.nit

# This file is part of NIT ( http://www.nitlanguage.org ).
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

# Parser for inline markdown
#
# Used to create the AST representation of inline nodes like emphasis, code, links
# images etc.
module markdown_inline_parsing

import markdown_ast

# Parser for inline content (text, links, emphasis, etc)
class MdInlineParser

        # List of delimiter processors to use
        private var delimiter_processors: Array[MdDelimiterProcessor] is lazy do
                var delimiters = new Array[MdDelimiterProcessor]
                delimiters.add new MdAsteriskDelimiterProcessor
                delimiters.add new MdUnderscoreDelimiterProcessor
                return delimiters
        end

        # Map special characters to their delimiter processor
        private var delimiter_processors_map: Map[Char, MdDelimiterProcessor] is lazy do
                var map = new HashMap[Char, MdDelimiterProcessor]
                for delimiter_processor in delimiter_processors do
                        add_delimiter_processor(delimiter_processor, map)
                end
                special_characters.add_all map.keys
                return map
        end

        # Register a delimiter processor
        private fun add_delimiter_processor(delimiter_processor: MdDelimiterProcessor, map: Map[Char, MdDelimiterProcessor]) do
                var opening = delimiter_processor.opening_delimiter
                var closing = delimiter_processor.closing_delimiter
                if opening == closing then
                        if map.has_key(opening) then
                                var old = map[opening]
                                if old.opening_delimiter == old.closing_delimiter then
                                        var s: MdStaggeredDelimiterProcessor
                                        if old isa MdStaggeredDelimiterProcessor then
                                                s = old
                                        else
                                                s = new MdStaggeredDelimiterProcessor(opening)
                                                s.add old
                                        end
                                        s.add delimiter_processor
                                        map[opening] = s
                                else
                                        add_delimiter_processor_for_char(opening, delimiter_processor, map)
                                end
                        else
                                add_delimiter_processor_for_char(opening, delimiter_processor, map)
                        end
                else
                        add_delimiter_processor_for_char(opening, delimiter_processor, map)
                        add_delimiter_processor_for_char(closing, delimiter_processor, map)
                end
        end

        # Register a delimiter processor for a special character
        private fun add_delimiter_processor_for_char(delimiter_char: Char, delimiter_processor: MdDelimiterProcessor, map: Map[Char, MdDelimiterProcessor]) do
                assert not map.has_key(delimiter_char) else
                        print "Delimiter processor conflict with delimiter char `{delimiter_char}`"
                end
                map[delimiter_char] = delimiter_processor
        end

        # List of characters that have a special Markdown meaning
        private var special_characters: Array[Char] = ['\n', '`', '[', ']', '\\', '!', '<', '&']

        # Link references by ID, needs to be built up using `parse_reference` before calling `parse`
        private var reference_map = new HashMap[String, MdLink]

        # Current block under parsing
        private var block: MdNode is noinit

        # Current input string
        private var input: String is noinit

        # Current index
        private var index: Int is noinit

        # Current line
        private var line: Int is noinit

        # Current column
        private var column: Int is noinit

        # Current column offset
        private var column_offset: Int is noinit

        # Top delimiter (emphasis, strong emphasis or custom emphasis)
        # Brackets are on a separate stack, different from the algorithm described in the spec.
        private var last_delimiter: nullable MdDelimiter = null

        # Top opening bracket (`[` or `![`)
        private var last_bracket: nullable MdBracket = null

        # Parse `input` as inline and add resulting nodes as children to `block`
        fun parse(input: String, offset: Int, block: MdNode) do
                self.block = block
                self.input = input.trim
                self.index = 0
                self.last_delimiter = null
                self.last_bracket = null
                self.line = block.location.line_start
                self.column_offset = offset
                self.column = 1 + column_offset

                var more_to_parse = parse_inline
                while more_to_parse do
                        more_to_parse = parse_inline
                end

                process_delimiters(null)
                merge_child_text_nodes(block)
        end

        # Advance the current index of `count` characters
        private fun advance(count: Int) do
                index += count
                column += count
        end

        # Attempt to parse a link reference
        #
        # Return how many characters were parsed as a reference.
        # Returns 0 if none.
        fun parse_reference(input: String): Int do
                self.input = input
                self.index = 0
                self.column = 0
                var dest
                var title
                var match_chars
                var start_index = index

                # label
                match_chars = parse_link_label
                if match_chars == 0 then return 0
                advance match_chars

                var raw_label = input.substring(0, match_chars)

                # colon
                if peek != ':' then return 0
                advance 1

                # link url
                spnl

                dest = parse_link_destination.first
                if dest == null or dest.is_empty then return 0

                var before_title = index
                var before_column = column
                spnl
                title = parse_link_title
                if title == null then
                        # rewind before spaces
                        index = before_title
                        column = before_column
                end

                var at_line_end = true
                if index != input.length and match(re_line_end) == null then
                        if title == null then
                                at_line_end = false
                        else
                                # the potential title we found is not at the line end,
                                # but it could still be a legal link reference if we discard the title
                                title = null
                                # rewind before spaces
                                index = before_title
                                column = before_column
                                # and instead check if the link URL is at the line end
                                at_line_end = match(re_line_end) != null
                        end
                end

                if not at_line_end then return 0

                var normalized_label = raw_label.normalize_reference
                if normalized_label.is_empty then return 0

                if not reference_map.has_key(normalized_label) then
                        var link = new MdLink(new MdLocation(0, 0, 0, 0), dest, title)
                        reference_map[normalized_label] = link
                end

                return index - start_index
        end

        # Line end pattern
        private var re_line_end: Regex = "^ *(\n|$)".to_re

        # Append standard text to the current block
        #
        # Read `text` between `begin_index` and `end_index`.
        private fun append_text(text: String, begin_index, end_index: nullable Int): MdText do
                var node: MdText
                if begin_index != null and end_index != null then
                        var nb_chars = end_index - begin_index
                        var string = text.substring(begin_index, nb_chars)
                        node = new MdText(
                                new MdLocation(
                                        line,
                                        column,
                                        line,
                                        column + nb_chars - 1
                                ), string)
                else
                        node = new MdText(
                                new MdLocation(
                                        line,
                                        column,
                                        line,
                                        column + text.length
                                ), text)
                end
                append_node(node)
                return node
        end

        # Append `node` to the current block
        private fun append_node(node: MdNode) do block.append_child(node)

        # Parse the next inline element in subject, advancing input index
        #
        # On success, add the result to block's children and return true.
        # On failure, return false.
        private fun parse_inline: Bool do
                var res: Bool
                var c = peek
                if c == '\0' then return false
                if c == '\n' then
                        res = parse_newline
                else if c == '\\' then
                        res = parse_backslash
                else if c == '`' then
                        res = parse_backticks
                else if c == '[' then
                        res = parse_open_bracket
                else if c == '!' then
                        res = parse_bang
                else if c == ']' then
                        res = parse_close_bracket
                else if c == '<' then
                        res = parse_auto_link or parse_html_inline
                else if c == '&' then
                        res = parse_entity
                else
                        if delimiter_processors_map.has_key(c) then
                                res = parse_delimiters(delimiter_processors_map[c], c)
                        else
                                res = parse_string
                        end
                end

                if not res then
                        advance 1
                        # When we get here, it's only for a single special character that turned
                        # out to not have a special meaning.
                        # So we shouldn't have a single surrogate here, hence it should be ok
                        # to turn it into a String
                        var literal = c.to_s
                        append_text(literal)
                end

                return true
        end

        # If `re` matches at current index in the input, advance index and return the match
        # Else return null.
        private fun match(re: Pattern): nullable String do
                if index >= input.length then return null
                var match = input.search_from(re, index)
                if match != null then
                        index = match.after
                        column = match.after
                        return match.to_s
                end
                return null
        end

        # Return the char at the current input index, or `\0`
        private fun peek: Char do
                if index < input.length then
                        return input.chars[index]
                end
                return '\0'
        end

        # Return the char at the current input index + 1, or `\0`
        private fun peek_next: Char do
                if index + 1 < input.length then
                        return input.chars[index + 1]
                end
                return '\0'
        end

        # Parse zero or more space characters, incuding at most one newline
        private fun spnl: Bool do
                var found_nl = false
                loop
                        var c = peek
                        if c == ' ' or c == '\t' then
                                advance 1
                                continue
                        else if c == '\n' then
                                if found_nl then break
                                found_nl = true
                                advance 1
                                continue
                        end
                        break
                end
                return true
        end

        # Parse a new line
        #
        # If it was preceded by two spaces, return a hard line break,
        # otherwise a soft line break
        private fun parse_newline: Bool do
                advance 1 # assume we're at a `\n`

                var last_child = block.last_child

                # check previous text for trailing spaces
                # the `has_suffix` is an optimization to avoid an RE match in the common case
                if last_child != null and last_child isa MdText and
                   (last_child.literal.has_suffix(" ")) then
                        var text = last_child
                        var literal = text.literal
                        var match = literal.search(re_final_space)
                        var spaces = if match != null then match.length else 0
                        if spaces > 0 then
                                text.literal = literal.substring(0, literal.length - spaces)
                        end
                        last_child.location.column_end = last_child.location.column_end - spaces
                        if spaces >= 2 then
                                append_node(new MdHardLineBreak(new MdLocation(line, column - spaces - 1, line, column - 1), false))
                        else
                                append_node(new MdSoftLineBreak(new MdLocation(line, column - spaces - 1, line, column -1)))
                        end
                else
                        append_node(new MdSoftLineBreak(new MdLocation(line, column - 1, line, column - 1)))
                end
                line += 1
                column = 1 + column_offset

                # gobble leading spaces in next line
                while peek == ' ' do
                        advance 1
                end
                return true
        end

        # Final white spaces pattern
        private var re_final_space: Regex = " *$".to_re

        # Parse a backslash-escaped special character
        #
        # Add either the escaped characters, a hard line break (if the backslash is followed by
        # a new line), or a literal backslash to the block's children.
        private fun parse_backslash: Bool do
                advance 1
                if peek == '\n' then
                        append_node(new MdHardLineBreak(new MdLocation(line, column - 1, line, column), true))
                        advance 1
                        line += 1
                        column = 1 + column_offset
                else if index < input.length and input.substring(index, 1).has(re_escapable) then
                    append_text(input, index, index + 1)
                    advance 1
                else
                        append_text("\\")
                end
                return true
        end

        # Escapable characters pattern
        private var p_escapable = "[]!\"#$%&\'()*+,./:;<=>?@\\[\\\\^_`\\\{|\\\}~-]"

        # Escapable characters regex
        private var re_escapable: Regex = "^{p_escapable}".to_re

        # Attempt to parse backticks
        #
        # Adding either a backtick code span or a literal sequence of backticks.
        private fun parse_backticks: Bool do
                var column_before = column
                var ticks = match(re_ticks_here)
                if ticks == null then return false

                var after_open_ticks = index
                var matched = match(re_ticks)
                while matched != null do
                        if matched == ticks then
                                var content = input.substring(after_open_ticks, index - after_open_ticks - ticks.length)
                                content = content.trim
                                content = content.replace(re_whitespace, " ")
                                var node = new MdCode(new MdLocation(line, column_before, line, column), matched.to_s, content.trim)
                                append_node(node)
                                column += 1
                                return true
                        end
                        matched = match(re_ticks)
                end
                # If we got here, we didn't match a closing backtick sequence
                index = after_open_ticks
                column = after_open_ticks + 1
                append_text(ticks)
                return true
        end

        # Backticks starting pattern
        private var re_ticks_here: Regex = "^`+".to_re

        # Backticks pattern
        private var re_ticks: Regex = "`+".to_re

        # Attempt to parse delimiters like emphasis, strong emphasis or custom delimiters
        private fun parse_delimiters(delimiter_processor: MdDelimiterProcessor, delimiter_char: Char): Bool do
                var res = scan_delimiters(delimiter_processor, delimiter_char)
                if res == null then return false

                var length = res.count
                var start_index = index
                var start_column = column

                advance length
                var column_before = column
                column = start_column
                var node = append_text(input, start_index, index)
                column = column_before

                # Add entry to stack for this opener
                var last_delimiter = new MdDelimiter(node, delimiter_char, res.can_open, res.can_close, last_delimiter)
                last_delimiter.length = length
                last_delimiter.original_length = length

                var prev = last_delimiter.prev
                if prev != null then
                        prev.next = last_delimiter
                end
                self.last_delimiter = last_delimiter
                return true
        end

        # Add open bracket to delimiter stack and add a text node to block's children
        private fun parse_open_bracket: Bool do
                var start_index = index
                advance 1

                var node = append_text("[")

                # Add entry to stack for this opener
                add_bracket(new MdBracket.link(node, start_index, column - 1, last_bracket, last_delimiter))
                return true
        end

        # If next character is `[`, add `!` delimiter to delimiter stack and add a text node to
        # block's children.
        # Otherwise just add a text node.
        private fun parse_bang: Bool do
                var start_index = index
                advance 1

                if peek == '[' then
                        advance 1
                        var node = append_text("![")

                        # Add entry to stack for this opener
                        add_bracket(new MdBracket.image(node, start_index + 1, column - 2, last_bracket, last_delimiter))
                else
                        append_text("!")
                end
                return true
        end

        # Try match close bracket against an opening delimiter stack
        #
        # Add either a link or image, or a plan `[` character, to block's children.
        # If there is a matching delimiter, remove it from the delimiter stack.
        private fun parse_close_bracket: Bool do
                advance 1
                var start_index = index
                var start_column = column

                # Get previous `[` or `![`
                var opener = last_bracket
                if opener == null then
                        # no matching opener, just return a literal
                        append_text("]")
                        return true
                end

                if not opener.allowed then
                        # matching opener but it's not allowed, juste return a literal
                        append_text("]")
                        remove_last_bracket
                        return true
                end

                # check to see if we have a link or image
                var dest: nullable Couple[nullable String, Bool] = null
                var title = null
                var is_link_or_image = false

                # maybe an inline link like `[foo](\uri "title")`
                if peek == '(' then
                        advance 1
                        spnl
                        dest = parse_link_destination
                        if dest.first != null then
                                spnl
                                # title needs a whitespace before
                                if input.substring(index - 1, 1).has(re_whitespace) then
                                        title = parse_link_title
                                        spnl
                                end
                                if peek == ')' then
                                        advance 1
                                        is_link_or_image = true
                                else
                                        index = start_index
                                        column = start_column
                                end
                        end
                end

                # maybe a reference link like `[foo][bar]`, `[foo][]` or `[foo]`
                if not is_link_or_image then
                        # see if there's a link label like `[bar]` or `[]`
                        var before_label = index
                        var label_length = parse_link_label
                        advance label_length
                        var ref = null
                        if label_length > 2 then
                                ref = input.substring(before_label, label_length)
                        else if not opener.bracket_after then
                                # If the second label is empty `[foo][]` or missing `[foo]`, then the first label
                                # is the reference.
                                # But it can only be a reference when there's no (unescaped) bracket in it.
                                # If there is, we don't even need to try to lookup the reference.
                                ref = input.substring(opener.index, start_index - opener.index)
                        end

                        if ref != null then
                                var nref = ref.normalize_reference
                                if reference_map.has_key(nref) then
                                        var link = reference_map[nref]
                                        dest = new Couple[nullable String, Bool](link.destination, false)
                                        title = link.title
                                        is_link_or_image = true
                                end
                        end
                end

                if is_link_or_image then
                        # If we got here, open is a potential opener
                        var link_or_image: MdLinkOrImage
                        if opener.is_image then
                                link_or_image = new MdImage(new MdLocation(line, opener.column, line, column - 1), dest.as(not null).first or else "", title)
                        else
                                link_or_image = new MdLink(new MdLocation(line, opener.column, line, column - 1), dest.as(not null).first or else "", title)
                        end
                        link_or_image.has_brackets = dest.as(not null).second

                        var node = opener.node.next
                        while node != null do
                                var next = node.next
                                link_or_image.append_child(node)
                                node = next
                        end
                        append_node(link_or_image)

                        # Process delimiters such as emphasis inside a link/image
                        process_delimiters(opener.prev_delimiter)
                        merge_child_text_nodes(link_or_image)
                        # We don't need the corresponding text node anymore, we turned it into a node
                        opener.node.unlink
                        remove_last_bracket

                        # Links within links are not allowed
                        # We found this link, so there can be no other link around it.
                        if not opener.is_image then
                                var bracket = last_bracket
                                while bracket != null do
                                        if not bracket.is_image then
                                                # disallow link opener
                                                bracket.allowed = false
                                        end
                                        bracket = bracket.prev
                                end
                        end
                        return true
                end

                if not is_link_or_image then
                        if parse_wikilink then return true
                end

                # no link or image
                append_text("]")
                remove_last_bracket
                index = start_index
                column = start_column
                return true
        end

        # Whitespace pattern
        private var re_whitespace: Regex = "\\s+".to_re

        # Add a bracket token on top of the `last_bracket` stack
        private fun add_bracket(bracket: MdBracket) do
                var last_bracket = self.last_bracket
                if last_bracket != null then
                        last_bracket.bracket_after = true
                end
                self.last_bracket = bracket
        end

        # Remove the last bracket on the `last_bracket` stack
        private fun remove_last_bracket do
                var last_bracket = self.last_bracket
                if last_bracket == null then return
                self.last_bracket = last_bracket.prev
        end

        # Wikilink placeholder
        #
        # Will be defined in sub module.
        private fun parse_wikilink: Bool do return false

        # Attempt to parse a link destination, returning the string or null if not match
        private fun parse_link_destination: Couple[nullable String, Bool] do
                var buffer = new Buffer

                var c = peek
                var parens = 0

                var has_bracket = c == '<'
                if has_bracket then advance 1

                loop
                        c = peek
                        if c == '\0' then
                                break # end of input
                        else if c == ' ' or c == '\t' or c == '\n' or c == '\r' then
                                break # no spaces allowed in urls
                        else if c == '\\' then
                                var next = peek_next
                                if escapable.has(next) then
                                        buffer.add next
                                        advance 2 # skip over the backslash
                                        continue
                                end
                        else if has_bracket and c == '>' then
                                advance 1
                                break
                        else if not has_bracket and c == '(' then
                                parens += 1
                        else if not has_bracket and c == ')' then
                                if parens == 0 then break
                                parens -= 1
                        else if c == '\0' then
                                break
                        end
                        buffer.add c
                        advance 1
                end
                return new Couple[nullable String, Bool](buffer.to_s, has_bracket)
        end

        # Attempt to parse a link title (sans quotes), returning the string or null if no match
        private fun parse_link_title: nullable String do
                var c = peek
                if c != '\'' and c != '"' and c != '(' then
                        return null
                end
                var opener = c

                var buffer = new Buffer
                loop
                        advance 1
                        c = peek
                        if c == opener or (opener == '(' and c == ')') then
                                advance 1
                                break
                        else if c == '\\' then
                                var next = peek_next
                                if escapable.has(next) then
                                        buffer.add next
                                        advance 1
                                        continue
                                end
                        else if c == '\0' then
                                return null
                        end
                        buffer.add c
                end
                return buffer.to_s
        end

        # Escapable characters
        private var escapable = "[]!\"#$%&\'()*+,./:;<=>?@\\^_`\{|\}~-"

        # Attempt to parse a link label returning number of characters parsed
        private fun parse_link_label: Int do
                var i = index
                while i < input.length do
                        var c = input[i]
                        if i == index and c != '[' then
                                return 0
                        else if c == '[' and i != index then
                                if input[i - 1] != '\\' or (i - 2 > index and input[i - 2] == '\\') then
                                        return 0
                                end
                        else if c == ']' then
                                if i > 1001 then return 0
                                if input[i - 1] != '\\' or (i - 2 > index and input[i - 2] == '\\') then
                                        return (i - index) + 1
                                end
                        end
                        i += 1
                end
                return 0
        end

        # Attempt to parse an autolink (URL or email in pointy brackets)
        private fun parse_auto_link: Bool do
                var column_before = column
                var m = match(re_autolink_email)
                if m != null then
                        var dest = m.substring(1, m.length - 2)
                        var node = new MdLink(new MdLocation(line, column_before, line, column), "mailto:{dest}", null, true)
                        node.append_child(new MdText(new MdLocation(line, column_before + 1, line, column - 1), dest))
                        column += 1
                        append_node(node)
                        return true
                end
                m = match(re_autolink_url)
                if m != null then
                        var dest = m.substring(1, m.length - 2)
                        var node = new MdLink(new MdLocation(line, column_before, line, column), dest, null, true)
                        node.append_child(new MdText(new MdLocation(line, column_before + 1, line, column - 1), dest))
                        column += 1
                        append_node(node)
                        return true
                end
                return false
        end

        # Autolink email pattern
        private var re_autolink_email: Regex = "^<([a-zA-Z0-9.!#$%&'*+/=?^_`\{|\}~-]+@[a-zA-Z0-9]([a-zA-Z0-9-]\{0,61\}[a-zA-Z0-9])?(\\.[a-zA-Z0-9]([a-zA-Z0-9-]\{0,61\}[a-zA-Z0-9])?)*)>".to_re

        # Autolink url pattern
        private var re_autolink_url: Regex = "^<[a-zA-Z][a-zA-Z0-9.+-]\{1,31\}:[^<> ]*>".to_re

        # Attempt to parse an inline HTML string
        private fun parse_html_inline: Bool do
                var column_before = column
                var m = match(re_html_tag)
                if m != null then
                        var node = new MdHtmlInline(new MdLocation(line, column_before, line, column), m)
                        column += 1
                        append_node(node)
                        return true
                end
                return false
        end

        private var p_tagname = "[A-Za-z][A-Za-z0-9-]*"
        private var p_attribute_name = "[a-zA-Z_:][a-zA-Z0-9:._-]*"
        private var p_uquoted_value = "[^\"'=<>` \t\n]+"
        private var p_squoted_value = "'[^']*'"
        private var p_dquoted_value = "\"[^\"]*\""
        private var p_attribute_value = "({p_uquoted_value}|{p_squoted_value}|{p_dquoted_value})"
        private var p_attribute_value_spec = "(\\s*=\\s*{p_attribute_value})"
        private var p_attribute = "(\\s{p_attribute_name}{p_attribute_value_spec}?)"
        private var p_opentag = "<{p_tagname}{p_attribute}*\\s*/?>"
        private var p_closetag = "</{p_tagname}\\s*[>]"
        private var p_html_comment = "<!---->|<!--(-?[^>-])(-?[^-])*-->"
        private var p_processing_instruction = "[<][?].*?[?][>]"
        private var p_declaration = "<![A-Z]+\\s+[^>]*>"
        private var p_cdata = "<!\\[CDATA\\[.*\\]\\]>"
        private var p_html_tag = "({p_opentag}|{p_closetag}|{p_html_comment}|{p_processing_instruction}|{p_declaration}|{p_cdata})"

        # HTML tag pattern
        private var re_html_tag: Regex do
                var re = "^{p_html_tag}".to_re
                re.ignore_case = true
                return re
        end

        # Attempt to parse an HTML entity
        private fun parse_entity: Bool do
                var m = match(re_entity_here)
                if m != null then
                        append_text(m)
                        return true
                end
                return false
        end

        # HTML entity pattern
        private var re_entity_here: Regex do
                var re = "^&(#x[a-f0-9]\{1,8\}|#[0-9]\{1,8\}|[a-z][a-z0-9]\{1,31\});".to_re
                re.ignore_case = true
                return re
        end

        # Parse a run of ordinary characters
        #
        # Or a single character with a special meaning in markdown, as a plain string.
        private fun parse_string: Bool do
                var begin = index
                var begin_column = column
                var length = input.length
                while index != length do
                        if special_characters.has(input.chars[index]) then
                                break
                        end
                        advance 1
                end
                if begin != index then
                        var column_before = column
                        column = begin_column
                        append_text(input, begin, index)
                        column = column_before
                        return true
                end
                return false
        end

        # Scan a sequence of characters with code `delimiter_char`
        #
        # Return information about the number of delimiters and whether they are positioned
        # such as they can open and/or close emphasis or strong emphasis.
        private fun scan_delimiters(delimiter_processor: MdDelimiterProcessor, delimiter_char: Char): nullable MdDelimiterData do
                var start_index = index
                var start_column = column

                var delimiter_count = 0
                while peek == delimiter_char do
                        delimiter_count += 1
                        advance 1
                end

                if delimiter_count < delimiter_processor.min_length then
                        index = start_index
                        column = start_column
                        return null
                end

                var before = "\n"
                if start_index > 0 then
                        before = input.substring(start_index - 1, 1)
                end

                var char_after = peek
                var after = "\n"
                if char_after != '\0' then
                        after = char_after.to_s
                end

                var before_is_punctuation = before.has(re_punctuation)
                var before_is_whitespace = before.has(re_whitespace_char)
                var after_is_punctuation = after.has(re_punctuation)
                var after_is_whitespace = after.has(re_whitespace_char)

                var left_flanking = not after_is_whitespace and
                        (not after_is_punctuation or before_is_whitespace or before_is_punctuation)
                var right_flanking = not before_is_whitespace and
                        (not before_is_punctuation or after_is_whitespace or after_is_punctuation)

                var can_open
                var can_close
                if delimiter_char == '_' then
                        can_open = left_flanking and (not right_flanking or before_is_punctuation)
                        can_close = right_flanking and (not left_flanking or after_is_punctuation)
                else
                        can_open = left_flanking and delimiter_char == delimiter_processor.opening_delimiter
                        can_close = right_flanking and delimiter_char == delimiter_processor.closing_delimiter
                end

                index = start_index
                column = start_column
                return new MdDelimiterData(delimiter_count, can_open, can_close)
        end

        # Punctuation pattern
        private var re_punctuation: Regex = "^[]!\"#\\$%&'()*+,.:;<=>?@^_`\{|\}~[-]".to_re

        # Whitespace character start pattern
        private var re_whitespace_char: Regex = "^[  \t\r\n]".to_re

        # Process the stack of delimiters
        private fun process_delimiters(stack_bottom: nullable MdDelimiter) do
                var openers_bottom = new HashMap[Char, nullable MdDelimiter]

                # find first closer above stack bottom
                var closer = last_delimiter
                while closer != null and closer.prev != stack_bottom do
                        closer = closer.prev
                end
                # move forward, looking for closers, and handling each
                while closer != null do
                        var delimiter_char = closer.delimiter_char

                        if not closer.can_close then
                                closer = closer.next
                                continue
                        end

                        if not delimiter_processors_map.has_key(delimiter_char) then
                                closer = closer.next
                                continue
                        end

                        var delimiter_processor = delimiter_processors_map[delimiter_char]
                        var opening_delimiter_char = delimiter_processor.opening_delimiter

                        # Found delimiter closer. Now look back for first matching opener
                        var use_delims = 0
                        var opener_found = false
                        var potential_opener_found = false
                        var opener = closer.prev

                        while opener != null and opener != stack_bottom and (not openers_bottom.has_key(delimiter_char) or opener != openers_bottom[delimiter_char]) do

                                if opener.can_open and opener.delimiter_char == opening_delimiter_char then
                                        potential_opener_found = true
                                        use_delims = delimiter_processor.delimiter_use(opener, closer)
                                        if use_delims > 0 then
                                                opener_found = true
                                                break
                                        end
                                end
                                opener = opener.prev
                        end

                        if not opener_found then
                                if not potential_opener_found then
                                        # Set lower bound for future searches for openers.
                                        # Only do this when we didn't even have a potential opener
                                        # (one that matches the character and can open).
                                        # If an opener was rejected because of the number of delimiters
                                        # (e.g. because of the "multiple of 3" rule),
                                        # we want to consider it next time because the number of delimiter
                                        # can change as we continue processing.
                                        openers_bottom[delimiter_char] = closer.prev
                                        if not closer.can_open then
                                                # We can remove a closer that can't be an opener,
                                                # once we've seen there's no matching opener.
                                                remove_delimiters_keep_node(closer)
                                        end
                                end
                                closer = closer.next
                                continue
                        end

                        var opener_node = opener.as(not null).node
                        var closer_node = closer.node

                        # Remove number of used delimieters from stack and inline nodes
                        opener.as(not null).length -= use_delims
                        closer.length -= use_delims
                        opener_node.literal = opener_node.literal.substring(0,
                                opener_node.literal.length - use_delims)
                        closer_node.literal = closer_node.literal.substring(0,
                                closer_node.literal.length - use_delims)

                        remove_delimiters_between(opener, closer)
                        # The delimieter processor can re-parent the nodes between opener and closer,
                        # so make sure they're contiguous already.
                        # Exclusive because we want to keep opener/closer themselves.
                        merge_text_nodes_between_exclusive(opener_node, closer_node)
                        delimiter_processor.process(opener_node, closer_node, use_delims)

                        # Node delimieter characters left to process, so we can remove
                        # delimieter and the now empty node
                        if opener.as(not null).length == 0 then
                                remove_delimiters_and_node(opener)
                        end

                        if closer.length == 0 then
                                var next = closer.next
                                remove_delimiters_and_node(closer)
                                closer = next
                        end
                end

                # Remove all delimiters
                while last_delimiter != null and last_delimiter != stack_bottom do
                        remove_delimiters_keep_node(last_delimiter)
                end
        end

        # Remove all delimiters between `opener` and `closer`
        private fun remove_delimiters_between(opener, closer: nullable MdDelimiter) do
                if opener == null or closer == null then return

                var delimiter = closer.prev
                while delimiter != null and delimiter != opener do
                        var previous_delimiter = delimiter.prev
                        remove_delimiters_keep_node(delimiter)
                        delimiter = previous_delimiter
                end
        end

        # Remove the delimiter and the corresponding text node
        #
        # For used delimiters, e.g. `*` in `*foo*`.
        private fun remove_delimiters_and_node(delim: nullable MdDelimiter) do
                if delim == null then return

                var node = delim.node
                node.unlink
                remove_delimiter(delim)
        end

        # Remove the delimiter but keep the corresponding node as text
        #
        # For unused delimiters such as `_` in `foo_bar`.
        private fun remove_delimiters_keep_node(delim: nullable MdDelimiter) do
                remove_delimiter(delim)
        end

        # Remove the delimiter `delim`
        private fun remove_delimiter(delim: nullable MdDelimiter) do
                if delim == null then return

                var prev = delim.prev
                if prev != null then
                        prev.next = delim.next
                end
                var next = delim.next
                if next == null then
                        # top of stack
                        last_delimiter = prev
                else
                        next.prev = prev
                end
        end

        # Merge all nodes between `from` and `to` excluding `from` and `to`
        private fun merge_text_nodes_between_exclusive(from, to: nullable MdNode) do
                if from == null or to == null then return
                # no node between them
                if from == to or from.next == to then return
                merge_text_nodes_inclusive(from.next, to.prev)
        end

        # Merge all child nodes of `node` into one
        private fun merge_child_text_nodes(node: nullable MdNode) do
                if node == null then return
                # no children or just one child node, no need for merging
                if node.first_child == node.last_child then return
                merge_text_nodes_inclusive(node.first_child, node.last_child)
        end

        # Merge all nodes between `from` and `to` including `from` and `to`
        private fun merge_text_nodes_inclusive(from, to: nullable MdNode) do
                var first = null
                var last = null

                var node = from
                while node != null do
                        if node isa MdText then
                                var text = node
                                if first == null then first = text
                                last = text
                        else
                                merge_if_needed(first, last)
                                first = null
                                last = null
                        end
                        if node == to then break
                        node = node.next
                end
                merge_if_needed(first, last)
        end

        # Merge all nodes between `first` and `last`
        private fun merge_if_needed(first, last: nullable MdText) do
                if first != null and last != null and first != last then
                        var buffer = new Buffer
                        buffer.append(first.literal)
                        var node = first.next
                        var stop = last.next
                        while node != null and node != stop do
                                buffer.append(node.as(MdText).literal)
                                first.location.line_end = node.location.line_end
                                first.location.column_end = node.location.column_end
                                var unlink = node
                                node = node.next
                                unlink.unlink
                        end
                        var literal = buffer.write_to_string
                        first.literal = literal
                end
        end
end

# Custom delimiter processor for additional delimiters besides `_` and `*`
interface MdDelimiterProcessor

        # The character that marks the beginning of a delimited node
        #
        # Must not clash with anu built-in special characters.
        fun opening_delimiter: Char is abstract

        # The character that marks the ending of a delimited node
        #
        # Must not clash with anu built-in special characters.
        fun closing_delimiter: Char is abstract

        # Minimum number of delimiters characters that are needed to active this
        #
        # Must be at least one.
        fun min_length: Int is abstract

        # Determine how many (if any) of the delimiter characters should be used
        #
        # This allows implementations to decide how many characters to use based on the
        # properties of the delimiter runs.
        #
        # An implementation can also return 0 when it doesn't want to allow this particular
        # combination of delimiter runs.
        fun delimiter_use(opener, closer: MdDelimiter): Int is abstract

        # Process the matched delimiters
        #
        # For example, by wrapping the nodes between `opener` and `closer` in a new node,
        # or appending a new node after the opener.
        #
        # Note that removal of the delimiter from the delimiter nodes and unlinking
        # them is done by the caller.
        fun process(opener, closer: MdText, delimiter_use: Int) is abstract
end

# A delimiter is one or more of the same delimiter character
#
# Used for paired delimiters like emphasis or strong emphasis.
class MdDelimiter

        # Node containing the delimiter
        var node: MdText

        # Character used as delimiter
        var delimiter_char: Char

        # Can `self` open a delimiter?
        var can_open: Bool

        # Cant `self` close a delimiter?
        var can_close: Bool

        # Previous delimiter found
        var prev: nullable MdDelimiter

        # Next delimiter found
        var next: nullable MdDelimiter

        # The number of characters in this delimiter run that are left for processing
        var length = 1

        # The number of characters originally in this delimiter run
        #
        # At the start of processing, this is the same as `length`.
        var original_length = 1
end

# Opening bracket for links and images
class MdBracket

        # Node containing the bracket
        var node: MdText

        # Index of the bracket in the original string
        var index: Int

        # COlumn of the bracket
        var column: Int

        # Is this bracket opening an image?
        var is_image: Bool

        # Previous bracket
        var prev: nullable MdBracket

        # Previous delimiter
        var prev_delimiter: nullable MdDelimiter

        # Whether this bracket is allowed to form a link/image
        var allowed = true

        # Whether there is an unescaped bracket (opening or closing) anywhere after this bracket
        var bracket_after = false

        # Create a new bracket for a link
        init link(node: MdText, index: Int, column: Int, prev: nullable MdBracket, prev_delimiter: nullable MdDelimiter) do
                init(node, index, column, false, prev, prev_delimiter)
        end

        # Create a new bracket for an image
        init image(node: MdText, index: Int, column: Int, prev: nullable MdBracket, prev_delimiter: nullable MdDelimiter) do
                init(node, index, column, true, prev, prev_delimiter)
        end
end

# Data about a delimiter parsing
private class MdDelimiterData

        # Number of successive delimiters found
        var count: Int

        # Can this delimiter open an inline construct?
        var can_open: Bool

        # Can this delimiter close an inline construct?
        var can_close: Bool
end

# An implementation of MdDelimiterProcessor that dispatches all calls to others
#
# The sub processors called bepends on the length of the delimiter run.
# All child processors must have different minimum lengths.
# A given delimiter run is dispatched to the child with the largest acceptable minimum length.
# If not child is applicable, the one with the largest minimum length is chosen.
class MdStaggeredDelimiterProcessor
        super MdDelimiterProcessor

        # Delimiter character
        var delim: Char

        # Sub processors to apply
        var processors = new Array[MdDelimiterProcessor]

        redef var min_length = 0
        redef fun opening_delimiter do return delim
        redef fun closing_delimiter do return delim

        # Add a new sub delimiter processor
        fun add(dp: MdDelimiterProcessor) do
                var len = dp.min_length
                var i = 0
                while i < processors.length do
                        var p = processors[i]
                        assert len != p.min_length else
                                print "Cannot add two delimiter processor for `{delim}` " +
                                        "and mininimum length `{len}`"
                        end
                        if len > p.min_length then
                                break
                        end
                        i += 1
                end
                processors.insert(dp, i)
        end

        # Find the corresponding processor for a length of `len` delimiter characters
        fun find_processor(len: Int): MdDelimiterProcessor do
                for processor in processors do
                        if processor.min_length <= len then return processor
                end
                return processors.first
        end

        redef fun delimiter_use(opener, closer) do
                return find_processor(opener.length).delimiter_use(opener, closer)
        end

        redef fun process(opener, closer, delimiter_use) do
                find_processor(delimiter_use).process(opener, closer, delimiter_use)
        end
end

# A processor for emphasis tokens
class MdEmphasisDelimiterProcessor
        super MdDelimiterProcessor

        # Delimiter character
        var delimiter_char: Char

        redef var min_length = 1
        redef fun opening_delimiter do return delimiter_char
        redef fun closing_delimiter do return delimiter_char

        redef fun delimiter_use(opener, closer) do
                # "multiple of 3" rule for internal delimiter runs
                if (opener.can_close or closer.can_open) and
                   ((opener.original_length + closer.original_length) % 3 == 0) then
                        return 0
                end
                # calculate actual number of delimiters used from this closer
                if opener.length >= 2 and closer.length >= 2 then
                        return 2
                end
                return 1
        end

        redef fun process(opener, closer, delimiter_use) do
                var single_delimiter = opening_delimiter.to_s
                var emphasis: MdNode
                if delimiter_use == 1 then
                        emphasis = new MdEmphasis(
                                new MdLocation(
                                        opener.location.line_start,
                                        opener.location.column_start,
                                        closer.location.line_end,
                                        closer.location.column_end),
                                single_delimiter)
                else
                        emphasis = new MdStrongEmphasis(
                                new MdLocation(
                                        opener.location.line_start,
                                        opener.location.column_start + opener.literal.length,
                                        closer.location.line_end,
                                        closer.location.column_end - closer.literal.length),
                                "{single_delimiter}{single_delimiter}")
                end
                var tmp = opener.next
                while tmp != null and tmp != closer do
                        var next = tmp.next
                        emphasis.append_child(tmp)
                        tmp = next
                end
                opener.insert_after(emphasis)
        end
end

# Asterisk delimiters processor
class MdAsteriskDelimiterProcessor
        super MdEmphasisDelimiterProcessor
        noautoinit

        redef var delimiter_char = '*'
end

# Underscore delimters processor
class MdUnderscoreDelimiterProcessor
        super MdEmphasisDelimiterProcessor
        noautoinit

        redef var delimiter_char = '_'
end

# Utils

redef class String

        # Remove escape backslash from string
        fun unescape_string: String do
                if not has(re_escaped) then return self

                var buffer = new Buffer
                var match = search(re_escaped)
                var last_end = 0
                while match != null do
                        buffer.append substring(last_end, match.from - last_end)
                        buffer.append substring(match.from + 1, 1)
                        last_end = match.after
                        match = search_from(re_escaped, last_end)
                end
                if last_end < length then
                        buffer.append substring(last_end, length - last_end)
                end
                return buffer.to_s
        end

        # Normalize link reference names
        private fun normalize_reference: String do
                var stripped = self.substring(1, length - 2).trim
                var lowercase = stripped.to_lower # TODO utf-8
                return lowercase.replace(re_whitespace, " ")
        end
end

redef class Sys
        private var p_escapable = "[]!\"#$%&\'()*+,./:;<=>?@\\[\\\\^_`\\\{|\\\}~-]"
        private var re_escaped: Regex = "\\\\{p_escapable}".to_re
        private var re_whitespace: Regex = "\\s+".to_re
end