# 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 {
	## 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)
}

# 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)

#== Block markup ==#

# Inline HTML
/^[ \t]?[ \t]?[ \t]?<\/?[0-9A-Za-z]+/ {
	# if it isn't inside a list
	if (indentation() - 2 * list_level < 4) {
		STATE_set(STATE_HTML)
		soft_next()
	}
}
STATE_isset(STATE_HTML) {
	if (/^[ \t]*$/) {
		STATE_unset(STATE_HTML)
	}
	else {
		soft_next()
	}
}

# Fenced code blocks
STATE_isset(STATE_FENCED_CODEBLOCK) {
	if (fenced_class) {
		$0 = fenced_class $0
		fenced_class = ""
		soft_next()
	}
	$0 = "    " $0
}

# Code blocks (ending condition)
STATE_isset(STATE_CODEBLOCK) {
	# If ended codeblock
	if ((STATE_isset(STATE_FENCED_CODEBLOCK) && /    ```$/) ||
	    ! /^(    |\t|[ \t]*$)/ ||
	    (blockquote_level > 0 && empty0))
	{
		PNappnd("</code></pre>")
		STATE_unset(STATE_CODEBLOCK)
		emptyP1 = 1
		if (STATE_thenunset(STATE_FENCED_CODEBLOCK)) {
			next
		}
	}
	else if (!STATE_isset(STATE_BLOCKQUOTE)) {
		handle_codeblock()
		soft_next()
	}
}

# Blockquotes
blockquote_level > 0 && empty0 {
	STATE_unset(STATE_PARAGRAPH_P1)
	for (P1 = P1 ORS; blockquote_level > 0; --blockquote_level) {
		P1 = P1 "</blockquote>"
	}
}
/^>[ \t]/ {
	match($0, /^[> \t]*> /)
	level = substr($0, RSTART, RLENGTH)

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

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

# Code block (end)
STATE_isset(STATE_CODEBLOCK) { ## when in blockquote
	handle_codeblock()
	soft_next()
}

# Link definition
/^\[[^\]]+\]:[ \t]+.*/ { # line starts link definition
	next
}

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

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

# Lists
function end_list() {
	STATE_unset(STATE_LIST)

	if (list_level == 0) return
	PNappnd("</li></" (lists[list_level] == "." ? "o" : "u") "l>")
	--list_level
}
function start_list(level, type, shift) {
	STATE_set(STATE_LIST)
	brand_new = TRUE

	## Every two columns we define a new level
	level = int((level + 2) / 2)
	## If list definition is the first line inside a code block
	if (level - list_level >= 3) return

	## Make list_level = level - 1
	while (list_level < level - 1) {
		lists[++list_level] = ""
	}
	## Make list_level = level
	while (list_level > level) {
		end_list()
	}

	if (list_level == level && lists[list_level] != type) {
		end_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
	}
	else {
		PNappnd("</li>")
		P1 = P1 ORS "<li>"
	}
}
/^[ \t]*[*+-] / { ## Unordered list
	level = indentation()

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

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

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

	start_list(level, type, shift)
}
!brand_new && list_level > 0 && /[^ \t]/ { ## Non-list line
	level = int((indentation() + 2) / 2)
	sub("^[ \t]{1," lists_shift[list_level] "}", "")

	while (list_level >= level && emptyP1) {
		end_list()
	}
}
list_level > 0 {
	STATE_unset(STATE_PARAGRAPH)
	brand_new = FALSE
}

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

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

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

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

# Code blocks
function handle_codeblock() {
	## Autoescape & and <
	for (i = 1; match(substr($0, i), /&/); i += RSTART) {
		RSTART += i - 1
		sub_match("&amp;")
	}
	gsub(/</, "\\&lt;")
	gsub(/>/, "\\&gt;")

	if (STATE_isset(STATE_FENCED_CODEBLOCK)) {
		$0 = substr($0, 5)
	}
}
/^(    |\t)/ && /[^ \t]/ { ## New codeblock
	STATE_set(STATE_CODEBLOCK)
	handle_codeblock()
	$0 = "<pre><code>" $0
	soft_next()
}

# 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 ==#

# 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>")
	}
}

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

# 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)
}

# Emphasis
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
}
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 " ")
	}
}

{
	## 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)
}

# Footnote references
/\[\^[^\]]+\]/ {
	while (match($0, /\[\^[\]]+\]/)) {
	}
}

# 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>" }

# After all $0 parsing
{
	__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>")
	}

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

#== 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
}
function STATE_set(name) {
	STATE_unset(STATE_PARAGRAPH)
	__state[name] = TRUE
}
function STATE_assign(name, other) {
	__state[name] = __state[other]
}
function STATE_unset(name) {
	__state[name] = FALSE
}
function STATE_isset(name) {
	return __state[name]
}
function STATE_thenset(name) {
	if (!__state[name]) {
		STATE_set(name)
		return TRUE
	}
	return FALSE
}
function STATE_thenunset(name) {
	if (__state[name]) {
		STATE_unset(STATE_PARAGRAPH)
		__state[name] = FALSE
		return TRUE
	}
	return FALSE
}

#== Line information ==#

function indentation(    len) {
	save_match()
		match($0, /^[ \t]*/)
		len = RLENGTH
	restore_match()
	return len
}

#== Match handling ==#

function save_match() {
	backup_rstart = RSTART
	backup_rlength = RLENGTH
}
function restore_match() {
	RSTART = backup_rstart
	RLENGTH = backup_rlength
}


#== Other ==#

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

function PNappnd(value) {
	if (emptyP1) P2 = P2 ORS value
	else         P1 = P1 ORS value
}

function soft_next() {
	__buffered_print()

	STATE_unset(STATE_PARAGRAPH)
	next
}

function sub_match(replacement) {
	$0 = substr($0, 1, RSTART - 1) replacement substr($0, RSTART + RLENGTH)
}

function char(string, ind) {
	if (1 > ind || ind > length(string)) {
		return "";
	}
	return substr(string, ind, 1)
}