shithub: mc

ref: 9e4686498bb2536f923cb0d5517b8911e85e1239
dir: /interp.myr/

use std

use "types.use"

pkg regex =
	const exec	: (re : regex#, str : byte[:] -> std.option(byte[:][:]))
	const search	: (re : regex#, str : byte[:] -> std.option(byte[:][:]))
;;

const Zthr = 0 castto(rethread#)

const exec = {re, str
	re.str = str
	re.strp = 0
	run(re)
	match re.matched
	| `std.Some thr:
		if thr.mend[0] != str.len
			-> `std.None
		else
			-> `std.Some getmatches(re, thr)
		;;
	| `std.None:
		-> `std.None
	;;
}

const getmatches = {re, thr
	var ret
	var i

	ret = std.slalloc(re.nmatch)
	for i = 0; i < re.nmatch; i++
		if thr.mstart[i] != -1 && thr.mend[i] != -1
			ret[i] = re.str[thr.mstart[i]:thr.mend[i]]
		else
			ret[i] = [][:]
		;;
	;;
	-> ret
}

const run = {re
	var i, consumed
	var thr

	re.matched = `std.None
	re.runq = mkthread(re, 0)
	re.runq.mstart = std.slalloc(re.nmatch)
	re.runq.mend = std.slalloc(re.nmatch)
	for i = 0; i < re.nmatch; i++
		re.runq.mstart[i] = -1
		re.runq.mend[i] = -1
	;;
	while re.nthr > 0
		while re.runq != Zthr
			/* set up the next thread */
			thr = re.runq
			re.runq = thr.next

			trace(re, thr, "\nrunning tid=%z, ip=%z, c=%c\n", thr.tid, thr.ip, re.str[re.strp] castto(char))
			consumed = step(re, thr)
			while !consumed
				consumed = step(re, thr)
			;;

			if thr.dead
				thrfree(re, thr)
			elif !thr.matched
				thr.next = re.expired
				re.expired = thr
			;;
		;;
		re.runq = re.expired
		re.expired = Zthr
		if re.nthr > 0
			re.strp++
		;;
	;;
}

/* 
 Steps forward one instruction. Returns true if a byte of input was
 consumed, false otherwise.
*/
const step = {re, thr
	var str
	var mstart
	var mend

	str = re.str
	match re.prog[thr.ip]
	/* Char matching. Consume exactly one byte from the string. */
	| `Ibyte b:
		trace(re, thr, "\t%z:\tByte %b (%c)\n", thr.ip, b, b castto(char))
		if !in(re, str)
			die(re, thr, "end of string")
		elif b != str[re.strp]
			die(re, thr, "not right char")
		else
			thr.ip++
			trace(re, thr, "\t\tmatched %b with %b\n", b, str[re.strp])
		;;
	| `Irange (start, end):
		trace(re, thr, "\t%z:\tRange (%b, %b)\n", thr.ip, start, end)
		if !in(re, str) || start > str[re.strp] || end < str[re.strp]
			die(re, thr, "bad range")
		else
			thr.ip++
		;;
	/*
	  Non-consuming. All of these recursively call step() until
	  exactly one byte is consumed from the string.
	 */
	| `Ibol:
		trace(re, thr, "\t%z:\tBol\n", thr.ip)
		if re.strp == 0 || str[re.strp - 1] == '\n' castto(byte)
			thr.ip++
			-> false
		else
			die(re, thr, "not beginning of line")
		;;
	| `Ieol:
		trace(re, thr, "\t%z:\tEol\n", thr.ip)
		if re.strp == str.len || str[re.strp] == '\n' castto(byte)
			-> false
		else
			die(re, thr, "not end of line")
		;;
	| `Ilbra m:
		trace(re, thr, "\t%z:\tLbra %z\n", thr.ip, m)
		trace(re, thr, "\t\tmatch start = %z\n", re.strp)
		thr.mstart[m] = re.strp
		thr.ip++
		-> false
	| `Irbra m:
		trace(re, thr, "\t%z:\tRbra %z\n", thr.ip, m)
		thr.mend[m] = re.strp
		thr.ip++
		-> false
	| `Ifork (lip, rip):
		trace(re, thr, "\t%z:\tFork (%z, %z)\n", thr.ip, lip, rip)
		mstart = std.sldup(thr.mstart)
		mend = std.sldup(thr.mend)
		fork(re, thr, rip, mstart, mend)
		thr.ip = lip
		-> false
	| `Ijmp ip:
		trace(re, thr, "\t%z:\tJmp %z\n", thr.ip, ip)
		thr.ip = ip
		-> false
	| `Imatch:
		trace(re, thr, "\t%z:\tMatch\n", thr.ip)
		finish(re, thr)
		-> true
	;;
	-> true
}

const fork = {re, thr, ip, mstart, mend
	var thr

	thr = mkthread(re, ip)
	thr.next = re.runq
	thr.mstart = mstart
	thr.mend = mend
	re.runq = thr
}

const die = {re, thr, msg
	trace(re, thr, "\t\tdie %z: %s\n", thr.tid, msg)
	thr.dead = true
	re.nthr--
}

const finish = {re, thr
	trace(re, thr, "finish %z\n", tid)
	match re.matched
	| `std.Some t:	thrfree(re, t)
	| `std.None:
	;;
	re.matched = `std.Some thr
	thr.matched = true
	re.nthr--
}

var tid = 0

const mkthread = {re, ip
	var thr : rethread#

	thr = std.alloc()

	thr.next = Zthr

	thr.ip = ip
	thr.tid = tid++
	thr.dead = false
	thr.matched = false

	thr.mstart = [][:]
	thr.mend = [][:]

	re.nthr++

	-> thr
}

const thrfree = {re, thr
	/* 
	   free the dying thread, and shuffle the last
	   thread into the it's place in the thread list
	*/
	trace(re, thr, "\t\tcleanup %z\n", thr.tid)
	std.slfree(thr.mstart)
	std.slfree(thr.mend)
	std.free(thr)
}

const in = {re, str 
	-> re.strp < str.len
}

const trace : (re : regex#, thr : rethread#, msg : byte[:], args : ...) = {re, thr, msg, args
	if re.debug
		std.putv(msg, std.vastart(&args))
	;;
}