# Almost the entire canonical Markdown specification is supported
# https://daringfireball.net/projects/markdown/syntax
# Notable behavioural exceptions are:
# - Block-level HTML elements needn't be separated with blank lines
# - Lists are identation-aware. List items begin and continue after the same
#   identation with which the list beginning (e.g. "* " or "5. ") was written.
#   The benefit is that all Markdown is parsed as normal inside an item.
#
# [.] Non-standard features
#     [x] Strikethrough ~~...~~
#     [x] Superscript ^...^
#     [x] Subscript ~...~
#     [.] Footnote [^...] (with user customizations)
#     [x] Task list - [ ] (readonly)
#     [x] Definition lists
#         [x] Single line
#         [x] Multi-line
#     [x] Fenced code blocks ```lang ```
#     [ ] Tables
#     [x] Links
#         [x] Link destination (<link> inside anchors)
#         [x] Nested links
#
# No character classes have been used, since they aren't supported on every system

# Naming conventions:
# all caps - constants, do not assign to variable (directly)
# begins with "__" - internal, do not use

BEGIN {
	footnote_index = 1

	## This is used to convert email autolinks into a series of hex values
	## Escaped output of: awk 'BEGIN {for (i = 32; i <= 126; ++i){ printf("%c", i) } }'
	ascii = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
	for (i = 1; i < 97; ++i) {
		char_to_dec[char(ascii, i)] = 31 + i
	}

	## We do character escaping by substituting the escape with some
	## "useless" characters, which we're confident won't appear in actual text.
	## These are from decimal value 14 to 28 inclusive. They're blank characters,
	## related to shifting, device control and data transmission.
	escapable = "\\`*_{}[]()#+-.!^~"
	for (i = 1; i < 18; ++i) {
		escapes[char(escapable, i)] = sprintf("%c", 13 + i)
	}
}

{
	STATE_assign(STATE_PARAGRAPH_P1, STATE_PARAGRAPH)
	STATE_set(STATE_PARAGRAPH)

	empty0  = empty($0)
	emptyP1 = empty(P1)
}

#== Block markup ==#

#-- Blockquotes --#
blockquote_level > 0 && empty0 {
	STATE_unset(STATE_PARAGRAPH_P1)
	## Blockquote end also ends codeblock
	if (STATE_thenunset(STATE_CODEBLOCK)) {
		PNappnd("</code></pre>")
	}
	for (P1 = P1 ORS; blockquote_level > 0; --blockquote_level) {
		P1 = P1 "</blockquote>"
	}
}
/^>[ \t]/ {
	STATE_set(STATE_BLOCKQUOTE)

	## blevel is the amount of ">" in the beginning of the line
	## We also remove the leading ">...> " part
	match($0, /^[> \t]*> /)
	blevel = substr($0, RSTART, RLENGTH)

	$0 = substr($0, RSTART + RLENGTH)
	gsub(/[ \t]/, "", blevel)
	blevel = length(blevel)

	for (;blockquote_level < blevel; ++blockquote_level) {
		P1 = P1 "<blockquote>"
	}
	for (;blockquote_level > blevel; --blockquote_level) {
		P2 = P2 "</blockquote>"
	}
}
STATE_isset(STATE_BLOCKQUOTE) && $0 == ">" {
	$0 = ""
	empty0 = TRUE
}

#-- Remove list indentation --#
list_level > 0 && !empty0 && !is_blank() {
	level = int((indentation() + 2) / 2)
	sub("^[ \t]{1," lists_shift[list_level] "}", "")
}

#-- Inline HTML --#
!STATE_isset(STATE_CODEBLOCK) && /^[ \t]{0,3}<\/?[0-9A-Za-z]+/ {
	STATE_set(STATE_HTML)
	soft_next()
}
STATE_isset(STATE_HTML) {
	if (is_blank()) {
		STATE_unset(STATE_HTML)
	}
	else {
		soft_next()
	}
}

#-- Fenced code blocks --#
STATE_isset(STATE_FENCED_CODEBLOCK) {
	## We need to add <pre><code> to the start of the first line inside the fence
	## so we don't introduce leading newlines
	if (fenced_start) {
		$0 = fenced_start $0
		fenced_start = ""
		soft_next()
	}

	if (/^```/) {
		PNappnd("</code></pre>")
		STATE_unset(STATE_PARAGRAPH)
		STATE_unset(STATE_CODEBLOCK)
		STATE_unset(STATE_FENCED_CODEBLOCK)
		next
	}
}

#-- Code blocks --#
STATE_isset(STATE_CODEBLOCK) {
	if (!empty0 && !STATE_isset(STATE_FENCED_CODEBLOCK) && ! /^(    |\t)/) {
		PNappnd("</code></pre>")
		STATE_unset(STATE_CODEBLOCK)
	}
	else {
		escape_in_codeblock()
		soft_next()
	}
}

#-- Link definition (ignore) --#
/^\[[^\]]+\]:/ {
	next
}

#-- Escapes --#
/\\[-\\`*_{}\[\]()#+.!^~]/ { # has escaped char
	while (match($0, /\\[-\\`*_{}\[\]()#+.!^~]/)) {
		sub_match(escapes[char($0, RSTART + 1)])
	}
}

#-- Horizontal rule --#
/^(---+|- -( -)+|\*\*\*+|\* \*( \*)+|___+|_ _( _)+)$/ {
	STATE_unset(STATE_PARAGRAPH)
	$0 = "<hr/>"
}

#-- Lists --#
/^[ \t]*[*+-] / { ## Unordered list
	level = level + int(indentation() / 2)

	match($0, /^[ \t]*[*+-] /)
	type  = char($0, RSTART + RLENGTH - 2)
	shift = RLENGTH
	sub_match("")

	start_list(level, type, shift)
	level = 0
}
/^[ \t]*[0-9]+\. / { ## Ordered list
	level = level + int(indentation() / 2)

	type  = "."
	match($0, /^[^.]+\. /)
	shift = RLENGTH
	sub_match("")

	start_list(level, type, shift)
	level = 0
}
level > 0 && list_level > 0 && !is_blank() && emptyP1 { ## Non-list line
	while (list_level >= level) {
		end_list()
	}
}
list_level > 0 {
	STATE_unset(STATE_PARAGRAPH)
}

# start_list(level, type, shift)
#
# Adds a new list or list item, even when that requires closing other lists. Updates lists and list_level.
#
# level - indentation integer
# type  - one of ".", "o", "u"
# shift - where does the list contents start indent-wise
function start_list(level, type, shift) {
	STATE_set(STATE_LIST)

	## Every two columns we define a new level
	level = int((level + 2) / 2)

	## When new level is much more indented than current
	if (list_level < level - 1) {
		list_level = level - 1
	}
	## When new level is less indented than current
	while (list_level > level) {
		end_list()
	}
	## When list type was changed on the same level
	if (list_level == level && lists[list_level] != type) {
		end_list()
	}

	## Create a new list
	if (list_level < level || lists[list_level] != type) {
		P1 = P1 ORS "<" (type == "." ? "o" : "u") "l><li>"
		lists[level] = type
		lists_shift[level] = shift
		list_level = level
	}
	## Create a new list item
	else {
		PNappnd("</li>")
		P1 = P1 ORS "<li>"
	}
}

# end_list()
#
# Closes a list. Also unsets STATE_LIST and decrements list_level.
function end_list() {
	STATE_unset(STATE_LIST)

	if (list_level == 0) return
	PNappnd("</li></" (lists[list_level] == "." ? "o" : "u") "l>")
	--list_level
}

#-- Checklists --#
STATE_isset(STATE_LIST) && level == 0 && /^\[[x ]\][ \t]/ {
	checked = (char($0, 2) == "x") ? " checked=\"checked\"" : "";
	$0 = "<input type=\"checkbox\" disabled=\"disabled\"" checked \
	     "><label>" substr($0, 5) "</label>"
}

#-- Fenced code blocks (new) --#
/^[ \t]*```/ {
	STATE_set(STATE_FENCED_CODEBLOCK)
	STATE_set(STATE_CODEBLOCK)

	match(P1, /```[^ \t]*/)
	fenced_start = ""
	if (RLENGTH > 3) {
		fenced_start = " class=\"language-" tolower(substr(P1, RSTART + 3, RLENGTH - 3)) "\""
	}

	fenced_start = "<pre><code" fenced_start ">"
	next
}

#-- Code blocks (new) --#
/^(    |\t)/ && /[^ \t]/ {
	STATE_set(STATE_CODEBLOCK)
	escape_in_codeblock()
	$0 = "<pre><code>" $0
	soft_next()
}

# escape_in_codeblock()
#
# Escape &, < and > with the appropriate HTML entities. Meant to be used with codeblocks.
function escape_in_codeblock() {
	for (i = 1; match(substr($0, i), /&/); i += RSTART) {
		RSTART += i - 1
		sub_match("&amp;")
	}
	gsub(/</, "\\&lt;")
	gsub(/>/, "\\&gt;")
}

#-- Definition lists --#
STATE_isset(STATE_DEFINITION_LIST) {
	if (!empty0) {
		STATE_unset(STATE_PARAGRAPH)
	}
	else if (def_started) {
		P1 = P1 "</dd>"
	}

	if ((!empty0 &&  emptyP1 && /^: /) ||
	    ( empty0 && !emptyP1 && !def_started && P1 !~ /^<dd>/) ||
	    (!empty0 && !emptyP1 && !def_started && !/^: /))
	{
		STATE_unset(STATE_DEFINITION_LIST)
		P2 = P2 "</dl>"

		STATE_set(STATE_PARAGRAPH_P1)
		STATE_set(STATE_PARAGRAPH)
		P1 = "<p>" P1
	}

	if (/^: /) {
		def_started = TRUE
	}
	else if (empty0) {
		def_started = FALSE
	}
}
/^: / && !emptyP1 {
	sub(/^<p>/, "", P1)
	$0 = substr($0, 3)

	P1 = "<dt>" P1 "</dt>"
	if (STATE_thenset(STATE_DEFINITION_LIST)) {
		P1 = "<dl>" P1
	}
	$0 = "<dd>" $0
	def_started = TRUE

	STATE_unset(STATE_PARAGRAPH)
	STATE_unset(STATE_PARAGRAPH_P1)
}

#== Inline markup ==#

#-- Autoescape & --#
/&/ {
	for (i = 1; match(substr($0, i), /&/); i += RSTART) {
		RSTART += i - 1
		## Don't escape HTML entities
		if (substr($0, RSTART) ~ /&[A-Za-z0-9#]+;/) { continue }
		sub_match("&amp;")
	}
}
#-- Autoescape < --#
/ < / {
	gsub(/ < /, "\\&lt;")
}

#-- Automatic links --#
/<[^ \t<>]+>/ {
	## URL: <uri_scheme:...>
	while (match($0, /<[A-Za-z][-A-Za-z0-9+.]*:[^ \t<>]+>/)) {
		href = substr($0, RSTART + 1, RLENGTH - 2)
		sub_match("<a href=\"" href "\">" href "</a>")
	}

	## Email addresses, with support for quoted local part "..."@...
	## and ip address literal ...@[...]
	while (match($0, /<([^ \t<>]+|".+")@([-A-Za-z0-9]+\.[^ \t<>]+|\[[0-9A-Fa-f.:]+\])>/)) {
		href = substr($0, RSTART + 1, RLENGTH - 2)
		href_masked = ""
		## The original markdown blogpost calls for convertions of all
		## email characters into their hex values. Allegedly, this fools
		## many autoharvesting spam bots.
		for (i = length(href); i > 0; --i) {
			href_masked = sprintf("&#x%X;", char_to_dec[char(href, i)]) href_masked
		}
		## href="mailto:..."
		sub_match("<a href=\"&#x6D;&#x61;&#x69;&#x6C;&#x74;&#x6F;&#x3A;" href_masked "\">" href_masked "</a>")
	}
}

#-- Line break --#
/  $/ {
	sub(/[ \t]*  $/, "</br>")
}

#-- atx-style headers --#
/^[ \t]*#+/ {
	match($0, /#+/)
	if (RLENGTH <= 6) {
		## Remove prefix/suffix
		gsub(/^[ \t]*#+[ \t]*/, "")
		gsub(/[ \t]*#+[ \t]*$/, "")

		$0 = "<h" RLENGTH ">" $0 "</h" RLENGTH ">"
		STATE_unset(STATE_PARAGRAPH)
	}
}

#-- setex-style headers --#
!emptyP1 && /^[ \t]*(=|-)+[ \t]*$/ {
	hlevel = 1 + ($0 ~ /-/)
	P1 = "<h" hlevel ">" substr(P1, 4) "</h" hlevel ">"
	$0 = ""
	STATE_unset(STATE_PARAGRAPH)
}

#-- Footnote references --#
/\[\^[^\]]+\]/ {
	while (match($0, /\[\^[^\]]+\]/)) {
		footnote_name = substr($0, RSTART + 2, RLENGTH - 3)
		if (!footnote[footnote_name]) {
			sub_match("<sup>?" footnote_name "?</sup>")
		}
		else {
			fn = footnote[footnote_name]
			delete footnote[footnote_name]
			## Escapes for emphasis elements
			gsub(/_/,  "\\&#95;",  footnote_name)
			gsub(/\*/, "\\&#42;",  footnote_name)
			gsub(/~/,  "\\&#126;", footnote_name)
			gsub(/`/,  "\\&#96;",  footnote_name)
			gsub(/\^/, "\\&#94;",  footnote_name)

			footnote_short = substr(fn, 0, 97)
			if (length(fn) > 97) {
				footnote_short = footnote_short "..."
			}

			sub_match("<sup id=\"ref-" footnote_name "\">"                                    \
			          "<a href=\"#footnote-" footnote_name "\" title=\"" footnote_short "\">" \
			          (footnote_index++) "</a></sup>")

			footnote_tag = footnote_tag ORS "<li id=\"footnote-" footnote_name "\">" \
			               "<p>" fn "&emsp;<a href=\"#ref-" footnote_name "\">&#94;</a></p></li>"
		}
	}
}

#-- Emphasis --#
{
	## Make sure <em> is on the inside for long chains
	## E.g. *****a***** will be the same as ****_a_****
	surround("___"      , "<strong><em>", "</em></strong>")
	surround("\\*\\*\\*", "<strong><em>", "</em></strong>", 3)

	gsurround("__"    , "<strong>", "</strong>")
	gsurround("_"     , "<em>"    , "</em>")
	gsurround("\\*\\*", "<strong>", "</strong>", 2)
	gsurround("\\*"   , "<em>"    , "</em>", 1)
	gsurround("``"    , "<code>"  , "</code>")
	gsurround("`"     , "<code>"  , "</code>")

	gsurround("~~" , "<s>"     , "</s>")
	gsurround("~"  , "<sub>"   , "</sub>")
	gsurround("\\^", "<sup>"   , "</sup>", 1)
}

# surround(brace, left, right [, blen])
#
# Substitute the shortest leftmost "brace ... brace" with "left ... right".
#
# Since brace is used in a regex, you'll need to escape special characters. In such cases, you need to set blen (brace length) to the count of "real" characters.
function surround(brace, left, right, blen) {
	if (blen == "") { blen = length(brace) }
	if (match($0, brace (brace == "``" ? "." : "[^" brace "]") "+" brace)) {
		elem = left substr($0, RSTART + blen, RLENGTH - 2*blen) right
		if (brace == "``") { gsub("`", "\\&#96;", elem) }
		sub_match(elem)
		return 1;
	}
	return 0
}

# gsurround(brace, left, right [, blen])
#
# Same as surround, however it substitutes all non-overlapping occurrences.
function gsurround(brace, left, right, blen) {
	while (surround(brace, left, right, blen)) {}

	if (blen == 1) {
		gsub("\\\\", "", brace)
		## Surrounding a single character span with spaces should make it a
		## literal char. This is inelegant but functional.
		gsub(" " left  " ", " " brace " ")
		gsub(" " right " ", " " brace " ")
	}
}

#-- Links --#
/!?\[[^\]]*\] ?[(\[][^)\]]*[\])]/ {
	while (match($0, /!?\[[^\]]*\] ?[(\[][^)\]]*[\])]/)) {
		link = substr($0, RSTART, RLENGTH)
		save_match()

		## ](xxxxx)
		match(link, /\] ?[(\[][^)\]]*[\])]$/)
		has_space = char(link, RSTART + 1) == " "
		is_img    = char(link, 1) == "!"

		## ...[xxxxx](...)...
		text = substr(link, 2 + is_img, RSTART - 2 - is_img)
		## ...[...](xxxxx)...
		href = substr(link, RSTART + has_space + 2, RLENGTH - has_space - 3)

		title = "\"\""
		if (char(link, RSTART + RLENGTH - 1) == "]") { ## is reference link
			if (href == "") href = text # [...][]
			## [...]: ... "xxxxx"
			title = reference[href, "title"]
			## [...]: xxxxx "..."
			href = reference[href, "href"]
		}
		else if (match(href, /[ \t]"[^"]*"[ \t]*$/)) { ## has title
			## ...[...](... "xxxxx")...
			title = substr(href, RSTART + 1, RLENGTH - 1)
			## ...[...](xxxxx "...")...
			href  = substr(href, 1, RSTART - 1)
		}

		if (is_img) elem = "<img src=\"" href "\" alt=\"" text "\" title=" title ">"
		else        elem = "<a href=\"" href "\" title=" title ">" text "</a>"

		restore_match()
		sub_match(elem)
	}
}

#-- Paragraph --#
emptyP1 && !empty0 && STATE_isset(STATE_PARAGRAPH) { $0 = "<p>" $0 }
!emptyP1 && empty0 && STATE_isset(STATE_PARAGRAPH_P1) { P1 = P1 "</p>" }

#== Buffered printing ==#
# Output is buffered on multiple lines, held in these variables:
# P2 = last non-empty line before the previous line
# P1 = previous line
# $0 = current line
# N1 = next new line (N1 is always set by the user)

{
	__buffered_print()
}
function __buffered_print() {
	empty0  = empty($0)
	emptyP1 = empty(P1)

	if (empty0 && emptyP1) {
		++P1_repeats
	}
	else if (!empty0 && emptyP1) {
		P1 = $0
	}
	else {
		print P2
		while (P1_repeats > 0) {
			print ""
			--P1_repeats
		}
		P2 = P1
		P1 = $0
		if (empty0) {
			P1_repeats = 1
		}
	}

	if (!empty(N1)) {
		if (emptyP1) {
			P1 = N1
		}
		else {
			print P2
			while (P1_repeats > 0) {
				print ""
				--P1_repeats
			}
			P2 = P1
			P1 = N1
			N1 = ""
		}
	}

	## Fix escaped characters
	for (i = 1; i < 18; ++i) {
		esc = char(escapable, i)
		gsub(escapes[esc], esc, P2)
	}
}

END {
	if (STATE_isset(STATE_DEFINITION_LIST)) {
		PNappnd("</dl>")
	}
	if (STATE_isset(STATE_PARAGRAPH)) {
		$0 = $0 "</p>"
	}

	print P2
	while (P1_repeats > 0) {
		print ""
		--P1_repeats
	}
	if (!empty(P1)) { print P1 }
	print
	if (!empty(N1)) { print N1 }

	if (footnote_tag) {
		print ORS "<div class=\"footnotes\"><hr><ol>" footnote_tag "</ol></div>"
	}
}

# PNappnd(value)
#
# Append value to the previous non-empty line. If P1 is empty, then it's P2, otherwise P1.
function PNappnd(value) {
	if (emptyP1) P2 = P2 ORS value
	else         P1 = P1 ORS value
}

# soft_next()
#
# Print buffered and then do next.
function soft_next() {
	__buffered_print()

	STATE_unset(STATE_PARAGRAPH)
	next
}

#== Boolean "constants" ==#

BEGIN {
	FALSE = 0
	TRUE = 1
}

#== States system ==#
# To convey the current state of parsing, we're using "states"
# These are nothing more than variables and an array, storing "booleans"
# The main benefit is semantics and syntax usage
# (especially since we're using variables, editors will offer autocompletion)

BEGIN {
	# State definitions
	STATE_HTML = 0
	STATE_FENCED_CODEBLOCK = 1
	STATE_CODEBLOCK = 2
	STATE_BLOCKQUOTE = 3
	STATE_PARAGRAPH = 4
	STATE_PARAGRAPH_P1 = 5
	STATE_LIST = 6
	STATE_DEFINITION_LIST = 7
}

# STATE_set(name)
#
# Set the state to TRUE
function STATE_set(name) {
	STATE_unset(STATE_PARAGRAPH)
	__state[name] = TRUE
}

# STATE_unset(name)
#
# Set the state to FALSE
function STATE_unset(name) {
	__state[name] = FALSE
}

# STATE_assign(name, other)
#
# Set the value of the first state to the value of the second state.
function STATE_assign(name, other) {
	__state[name] = __state[other]
}

# STATE_isset(name)
#
# Return boolean
function STATE_isset(name) {
	return __state[name]
}

# STATE_thenset(name)
#
# If the state is not set, set it and return TRUE. Otherwise return FALSE.
function STATE_thenset(name) {
	if (!__state[name]) {
		STATE_set(name)
		return TRUE
	}
	return FALSE
}

# STATE_thenunset(name)
#
# If the state is set, unset it and return TRUE. Otherwise return FALSE.
function STATE_thenunset(name) {
	if (__state[name]) {
		STATE_unset(STATE_PARAGRAPH)
		__state[name] = FALSE
		return TRUE
	}
	return FALSE
}

#== Line information ==#

# indentation()
#
# Return the cound of leading blank characters in $0.
function indentation(    len) {
	save_match()
		match($0, /^[ \t]*/)
		len = RLENGTH
	restore_match()
	return len
}

# is_blank()
#
# Wether $0 contains only blank characters.
function is_blank() {
	return ! /[^ \t]/
}

#== Match handling ==#

# save_match()
#
# Backup RSTART and RLENGTH
function save_match() {
	backup_rstart = RSTART
	backup_rlength = RLENGTH
}

# restore_match()
#
# Restore RSTART and RLENGTH, from save_match's backup.
function restore_match() {
	RSTART = backup_rstart
	RLENGTH = backup_rlength
}

# sub_match(replacement)
#
# Replace the range, specified by RSTART and RLENGTH (from match function) with the given replacement. Replacement is not a regex.
function sub_match(replacement) {
	$0 = substr($0, 1, RSTART - 1) replacement substr($0, RSTART + RLENGTH)
}

#== Other ==#

function empty(value) {
	return value == ""
}

# char(string, ind)
#
# Return a single-character string, which is found at the given index. If the index is invalid, a blank string is returned.
function char(string, ind) {
	if (1 > ind || ind > length(string)) {
		return "";
	}
	return substr(string, ind, 1)
}