#!/usr/bin/ruby
# Description:	Test sparse allocator
PROGNAME = File.basename($0)

# Make sure this lets us load libExpr.rb
MYDIR = File.dirname($0)
LIBDIR = MYDIR	# Currently libExpr.rb is in the same dir as this testbench

#########################
# Verif::assert and other utils
#########################
class Verif
	def self.assert(val, msg = nil)
		val,msg = false,val if msg == nil
		return if val
		from = caller_locations(1,1).first
		$stderr.puts "[ASSERT] #{from}:\n[ASSERT]   #{msg}"
		exit(-1)
	end
end

class Rand
	class << self
		def seed(val = 0)
			puts "Random seed: #{val}"
			srand(val)
		end
		def rand(a,b=nil)
			return a[Random::rand(a.size)] if a.class==Array
			return Random::rand(a) unless b
			return a + Random::rand(b-a+1)
		end
		def prob(perc)
			rand(1,100) <= perc
		end
	end
end

class String
	def to_num
		return self.to_i(16) if self.match(/^0x/)
		return self.to_i(2)  if self.match(/^0b/)
		return self.to_i(8)  if self.match(/^0b/)
		puts "Converting string [#{self}] to number?" unless self.match(/^[\d\+-]+$/)
		self.to_i
	end
end

#########################
# libExpr
#########################
$LOAD_PATH.unshift File.expand_path(LIBDIR)
require 'libExpr'

Rand::seed(ARGV[0] ? ARGV[0].to_num : 0)

##################################################
# Testbench
# Make random expressions, and compare Expr.eval to eval
##################################################

# Put random parens around a exprArray
def randParens(exprArray, force = false)
	return exprArray unless force || Rand::prob(40)
	exprArray.unshift('(')
	exprArray.push(')')
	exprArray
end

# Make a random expression using operations on numbers/values and/or more expressions
# The top level(s) *might* be logical ops, like "a && b || c"	(a,b,c are logical, result logical)
# The bottom level(s) will likely be numeric ops, like  "a + b * c"	(a,b,c are numeric, result logical)
# At some point we (probably) switch from logical to numberic with ops like:  "a < b"	(a,b are numeric, result logical)
# Also consider special case of ternary op "a ? b : c" where a is logical, and b,c can be either numeric or logical
def randExpr(depth, logicalOp = Rand::prob(20), allowTernary = false)
	at = allowTernary	# alias
	logical_ops_on_nums = ['<', '<=', '>', '>=', '==', '!=']
	# Make '<<' and '>>' less likely, because they tend to cause numeric explosion/out of memory (100<<200<<150)
	numeric_ops_on_nums = ['*', '/', '%', '+', '-', '&', '^', '|', '*', '/', '%', '+', '-', '&', '^', '|', '<<', '>>']
	logical_ops_on_logic = ['&&', '||', '^']

	if allowTernary
		logical_ops_on_nums << '?:'
		numeric_ops_on_nums << '?:'
		numeric_ops_on_nums << '?:'
		logical_ops_on_logic << '?:'
	end

	# Next level is logical or numeric?
	logicalVals = logicalOp && Rand::prob(40)

	forceParens = (logicalOp && !logicalVals) ? true : false

	# Expression is a number, variable, or possibly an expression (until depth == 0)
	# We don't always descend, because we don't want perfectly balanced expressions
	descend = (depth != 0 && Rand::prob(20*depth))
	if descend
		ops = logical_ops_on_logic if logicalOp && logicalVals
		ops = logical_ops_on_nums if logicalOp && !logicalVals
		ops = numeric_ops_on_nums if !logicalOp
		op = Rand::rand(ops)

		# Special case:  ?: is not only a ternary op, but it is logical (conditions) and logical or numeric (expressions)
		if op == '?:'
			logicalVals = logicalOp	# Our expressions we choose from need to match whether we are logical or not.

			# We need an extra space before ':' since our labels can include ':' and we could think
			# that "var[:n1]:" is a label as opposed to two tokens, "var[:n1]" and ":"
			# We also need spaces around '?' - and that's even a ruby requirement.  "true?1:0" is a syntax error
			expr = [randExpr(depth-1, true, at), ' ? ', randExpr(depth-1, logicalVals, at), ' :', randExpr(depth-1, logicalVals, at)]
			# We probably need parens around the whole thing if it's a logical op on nums, because ?: is lower precedence
			# than other logical ops, so:  "4< true ? 1 : 2" is actually "(4<true)?99:1" which is an error
			# Or even if it's after a numeric op.  "4+ true ? 1 : 2" is "(4+true)..."
			forceParens = true
		else
			expr = [randExpr(depth-1,logicalVals, at), op, randExpr(depth-1, logicalVals, at)]
		end
	else
		simpleValues = logicalOp ?
			['var[:t0]','var[:t1]','var[:t2]','var[:f0]','var[:f1]','var[:f2]', 'true', 'false'] :
			['var[:n0]','var[:n1]','var[:n2]', '1', '3', '10', '42']
		expr = [Rand::rand(simpleValues)]
	end

	expr = randParens(expr, forceParens)

	# Any unary opts?
	if Rand::prob(25)
		unaryOps = logicalOp ? ['!'] : ['-','-','-','+']
		expr.unshift(Rand::rand(unaryOps))
		expr = randParens(expr)
	end

	# Join (with random spaces)
	spaces = Array.new(expr.size+1) { |i| ' '*Rand::rand(2) }
	return spaces.zip(expr).join('')
end

def rescueZeroDivAndMem
	begin
		result = yield
	rescue ZeroDivisionError => e
		divErr = true
	rescue NoMemoryError => e
		memErr = true
	end
	str = divErr ? "[div/0]" : result
	return str, result, divErr, memErr
end

def testEvalExpr
	Expr.useTrueFalse

	varLabel = '[a-zA-Z][a-zA-Z0-9_\.\[\]\:]*'
	var = Hash.new
	var[:t0] = var[:t1] = var[:t2] = true	# true vars
	var[:f0] = var[:f1] = var[:f2] = false	# false vars

	num = 1000
	depth=6
	num.times {
		var[:n0] = Rand::rand(10)	# rand nums
		var[:n1] = Rand::rand(10)
		var[:n2] = Rand::rand(10)
		allowTernary = Rand::prob(60)

		exprStr = randExpr(depth, nil, allowTernary)

		exprStr.gsub!('/0','')	# avoid some obvious divByZero failures

		puts "RandExpr: #{exprStr}"

		expr = Expr.new(exprStr, varLabel)

		astStr, astResult, astDiv0, astMem = rescueZeroDivAndMem {
			expr.evalAST { |name|
				Verif::assert(name.match(/^var\[\:(\S+)\]$/), "Unknown variable name? #{name}")
				var[$1.to_sym]
			}
		}

		if astMem
			puts "Memory overflow (maybe bignums too big?)"
			next
		end

		evalStr, evalResult, evalDiv0, evalMem = rescueZeroDivAndMem {
			eval(exprStr)
		}
		Verif::assert(!evalMem, "Memory overflow for eval but not AST??")

		# If we did '?:' then we can't do prefix/RPN, since they don't support it.
		if allowTernary && exprStr.match(/\?/)
			puts "	RESULTS: eval=#{evalStr}  ast=#{astStr}  (no pre/RPN due to '?:' operator)"
			Verif::assert("Expr doesn't match ast:\n\n#{exprStr}\n\n  With: #{var}") unless evalResult==astResult && evalDiv0 ==astDiv0
			next
		end

		rpnStr, rpnResult, rpnDiv0, rpnMem = rescueZeroDivAndMem {
			rpnResult = expr.evalRPN { |name|
				Verif::assert(name.match(/^var\[\:(\S+)\]$/), "Unknown variable name? #{name}")
				var[$1.to_sym]
			}
		}
		Verif::assert(!rpnMem, "Memory overflow for prefix but not AST??")

		preStr, preResult, preDiv0, preMem = rescueZeroDivAndMem {
			expr.evalPrefix { |name|
				Verif::assert(name.match(/^var\[\:(\S+)\]$/), "Unknown variable name? #{name}")
				var[$1.to_sym]
			}
		}
		Verif::assert(!preMem, "Memory overflow for prefix but not AST??")

		puts "	RESULTS: eval=#{evalStr}  ast=#{astStr}  pre=#{preStr} rpn=#{rpnStr}"
		Verif::assert("Expr doesn't match ast:\n\n#{exprStr}\n\n  With: #{var}") unless evalResult==astResult && evalDiv0 ==astDiv0
		Verif::assert("Expr doesn't match prefix:\n\n#{exprStr}\n\n  With: #{var}") unless evalResult==preResult && evalDiv0 ==preDiv0

		# Hack - because libExpr doesn't do short-circuit of || or &&, we can conceivably have
		# a ZeroDivisionError on expr but not eval.
		if rpnDiv0 && !evalDiv0 && exprStr.match(/\|\||&&/)
			puts "div/0 error for rpn, guessing it is due to missing short-circuit eval, skipping"
			next
		end

		Verif::assert("Expr doesn't match RPN:\n\n#{exprStr}\n\n  With: #{var}") unless evalResult==rpnResult && evalDiv0 ==rpnDiv0
	}
	exit
end

testEvalExpr