import types
import copy
import os
import sys
sys.path.append(os.environ['PYTHONPATH'] + '/covers_cpp')

import covers_hill
#import covers_cpp
gentree = None

GP = []

NONE = 0
# define output formats
FLATTEN = 1
NESTED = 2
CUSTOM = 3
# define gentree formats
XML = 1

def flatten(nested_terms):
	'''
	Purpose
		return the flattened version of nested_terms.
	Precondition
		nested_terms is a nested list of Term objects.
	'''
	string = ''
	for term in nested_terms:
		if isinstance(term,types.ListType):
			string += flatten(term)
		elif isinstance(term,T):
			string += str(term.name) + ' '
		else:
			string += str(term) + ' '
	return string

def nested_strings(nested_terminals):
	'''
	Purpose
		convert nested_terminals into a nested list of strings and
		 return the nested list of strings.
	Precondition
		nested_terminals is a nested list of T objects.
	'''
	L = []
	for element in nested_terminals:
		if isinstance(element,T): # element is terminal
			L.append(element.name)
		else: # element is list
			L.append( nested_strings(element) )
	return L

def is_ground(nested_terms):
	'''
	Purpose
		return True if nested_terms does not contain V, and False
		 otherwise.
	Precondition
		nested_terms is a nested list of Term objects.
	'''
	for term in nested_terms:
		if isinstance(term,types.ListType):
			if not is_ground(term):
				return False
		elif isinstance(term,V):
			return False
		elif isinstance(term,Terminal_generator):
			return False
	return True

class Sentential_form:
	'''
	a term is either an instance of V or T.
	a sentential form is a nested list of terms:
		Nesting is introduced whenever a variable is replaced by a
		rule's right hand side.
	a term's location is specified by the indexes in PP.
	'''
	def __init__(self,terms):
		'''
		Purpose
			create a Sentential_form object consisting of terms.
		Precondition
			terms is a reference to a list of Term objects.
		'''
		self.contents = terms

	def get_leftmost_nonterminal(self,PP=[]):
		'''
		Purpose
			return the parse tree path to the leftmost non-terminal.
		Precondition
			PP is the old parse tree path.
		'''
		contents = self.contents

		# copy needed for applying alternative rules
		new_PP = PP[:]
		while True:
			contents = self.get(new_PP)
			for i in range(len(contents)):
				if isinstance(contents[i],V) or \
				 isinstance(contents[i],Terminal_generator):
					new_PP.append( [i,None] )
					return new_PP
			if len(new_PP) > 0:
				new_PP.pop()
			else:
				break
		return None

	def get(self,PP):
		'''
		Purpose
			return the term or terms located in PP.
		Precondition
			PP is a stack of list index and rule pairs.
		'''
		contents = self.contents
		for list_index_rule_pair in PP:
			contents = contents[ list_index_rule_pair[0] ]
		return contents

	def replace(self,PP,rhs):
		'''
		Purpose
			replace the term located in PP by rhs.
		Precondition
			PP is a stack of list index and rule pairs.
			rhs is a reference to a list of terms.
		'''
		contents = self.contents
		for list_index_rule_pair in PP[:-1]:
			contents = contents[ list_index_rule_pair[0] ]
		contents[ PP[-1][0] ] = rhs

class Grammar:
	def __init__(self):
		'''
		Purpose
			create a Grammar object that does not contain any
			 rules.
		'''
		global gentree,FLATTEN,XML

		self.rules = {}
		self.output_format = FLATTEN
		self.gentree_format = XML
		gentree = __import__('gentree_xml')
		self.gentree_file = 'gentree.xml'
		self.num_rules = 0

	def append_rule(self,rule):
		'''
		Purpose
			add rule to grammar.
		Precondition
			rule is a Rule object.
		'''
		if not self.rules.has_key(rule.lhs):
			self.rules[rule.lhs] = []
		rule.id = len(self.rules[rule.lhs])
		rule.order = self.num_rules
		self.rules[rule.lhs].append(rule)
		self.num_rules += 1

	def set_output_format(self,format,format_function=None):
		'''
		Purpose
			set the output format to format.
			if format is CUSTOM, then format_function should be
			 provided. Otherwise, the format_function should be
			 omitted.
		Precondition
			format is FLATTEN, NESTED, CUSTOM, or NONE.
			format_function is a pointer to a function that takes
			 nested list of terminals as input.
		'''
		self.output_format = format
		self.output_format_function = format_function

	def get_output_format(self):
		'''
		Purpose
			return the output format.
		'''
		return self.output_format

	def set_gentree_format(self,format):
		'''
		Purpose
			set the gentree format to format.
		Precondition
			format is XML or NONE.
		'''
		global gentree,XML,NONE

		self.gentree_format = format
		if self.gentree_format == XML:
			gentree = __import__('gentree_xml')
		elif self.gentree_format == NONE:
			gentree = __import__('gentree_default')

	def get_gentree_format(self):
		'''
		Purpose
			return the gentree format.
		'''
		return self.gentree_format

	def set_gentree_file(self,file):
		'''
		Purpose
			set the gentree file to file.
		Precondition
			file is a string that contains valid path.
		'''
		self.gentree_file = file

	def get_gentree_file(self):
		'''
		Purpose
			return the gentree file.
		'''
		return self.gentree_file

	def create_gentree(self):
		'''
		Purpose
			return Gentree object.
		'''
		global gentree
		return gentree.Gentree(self.gentree_file)

	def generate_matching_rules(self,V):
		'''
		Purpose
			return rules that start with V.
		Precondition
			V is a V object.
		'''
		for rule in self.rules[V.name]:
			yield rule

	def format_output(self,S):
		'''
		Purpose
			return a string representation of S in output_format.
		Precondition
			S is a Sentential_form object.
		'''
		global FLATTEN,NESTED,CUSTOM,NONE

		if self.output_format == FLATTEN:
			return flatten(S.contents)
		elif self.output_format == NESTED:
			return S.contents
		elif self.output_format == CUSTOM:
			return self.output_format_function(S.contents)
		elif self.output_format == NONE:
			return ''

def default_precode():
	'''
	Purpose
		define a rule's default precode.
	'''
	return True

def default_postcode(s):
	'''
	Purpose
		define a rule's default postcode.
	Precondition
		s is a nested list of T objects.
	'''
	pass

class Rule:
	def __init__(self,tags,lhs,rhs):
		'''
		Purpose
			create a Rule object that consists of zero or more
			 tags, the left-hand side (lhs), and the right-hand
			 side (rhs).
		Precondition
			tags is a dictionary where the keys are tag names and
			 the values are tag values.
			lhs is a string.
			rhs is a reference to a list of terms.
		'''
		self.tags = tags
		self.lhs = lhs
		self.rhs = rhs
		self.id = None

		self.order = 0	# preserve textual order

		if not self.tags.has_key('precode'):
			self.tags['precode'] = default_precode
		if not self.tags.has_key('postcode'):
			self.tags['postcode'] = default_postcode
		self.precode = self.tags['precode']
		self.postcode = self.tags['postcode']

	def __repr__(self):
		'''
		Purpose
			return the string representation of a Rule object.
		'''
		return self.lhs + '.' + str(self.id)

class Term:
	def __init__(self,name):
		'''
		Purpose
			create a Term object named name.
		'''
		self.name = name

class T(Term):
	def __repr__(self):
		'''
		Purpose
			return the string representation of a T object.
		'''
		if isinstance(self.name,int):
			return str(self.name)
		elif isinstance(self.name,float):
			return str(self.name)
		return "'" + str(self.name) + "'"

class V(Term):
	def __repr__(self):
		'''
		Purpose
			return the string representation of a V object.
		'''
		return self.name

class Terminal_generator:
	def __init__(self,param_list):
		'''
		Purpose
			create a Terminal_generator object.
		'''
		self.param_list = param_list

	def generate(self):
		'''
		Purpose
			generate a list of terminals.
		'''
		for param in self.param_list:
			yield param

	def __repr__(self):
		'''
		Purpose
			return the string representation of a
			 Terminal_generator object.
		'''
		return self.__class__.__name__ + \
		 '(' + str(self.param_list) + ')'

class Range(Terminal_generator):
	def generate(self):
		'''
		Purpose
			generate count integers from start, incrementing the
			 value by skip after each derivation
		'''
		start = self.param_list[0]
		skip = self.param_list[1]
		count = self.param_list[2]

		for i in range(count):
			yield start
			start += skip

class List(Terminal_generator):
	pass

class File(Terminal_generator):
	def generate(self):
		'''
		Purpose
			for each line in file_name, one string is produced
		'''
		file_name = self.param_list[0]

		file_handle = open(file_name,'r')
		file_content = file_handle.read()
		file_handle.close()

		file_content = file_content[:-1] # get rid of EOF
		for line in file_content.split('\n'):
			yield line

def prune_tree(GP,PP,L):
	'''
	Purpose
		return False if for every rule R in GP, R.precode, R.rdepth,
		 R.depth and R.count return True
		return True otherwise
	Precondition
		GP: generation tree path
		PP: parse tree path
		L: generation tree object
	'''
	has_cov = False

	# execute precode for GP[-1]
	# if precode returns False, return True
	if not GP[-1].precode():
		return True

	# for each rule R in GP, rules visited from top to bottom
	GP_indexes = range(len(GP))
	GP_indexes.reverse()
	for i in GP_indexes:
		R = GP[i]

		if R.tags.has_key('cov'):
			has_cov = True

		if R.tags.has_key('rdepth'):
			# if R has {rdepth N} and R occurs more than N times
			# in PP, return True
			N = R.tags['rdepth']
			R_count = 0
			for list_index_rule_pair in PP:
				if list_index_rule_pair[1] == R:
					R_count += 1
			if R_count > N:
				return True

		if R.tags.has_key('depth'):
			# if R has {depth N} and R is in GP[-1-N] or below,
			# return True
			N = R.tags['depth']
			R_index = GP.index(R)
			top_index = len(GP) - 1
			if (top_index - R_index) >= N:
				return True

		if R.tags.has_key('count'):
			# if R has {count N} and
			# no rule with a cov tag is at or below R in GP
			# and L.get_count(R) >= N, return True
			N = R.tags['count']
			if has_cov:
				if R != GP[-1]:
					continue
			if L.get_count(i) >= N:
				return True

	return False

def generate_cov(G,R,PP,L):
	'''
	Purpose
		return a cover of R's cov tag over R.rhs
	Precondition
		G: grammar
		R: rule
		PP: parse tree path
		L: generation tree object
	'''
	# for each index_set/strength pair in R's cov tag
	for cov_spec in R.tags['cov']:
		parameter_trees = []
		(index_set,strength) = cov_spec

		L.log_start(gentree.parameter_trees,None,None,False)

		# for each term in R.rhs
		for term in R.rhs:
			parameter_tree = []
			S = Sentential_form( [term] )

			# generate term's parameter tree
			if isinstance(term,V):
				output_format = G.get_output_format()
				G.set_output_format(NESTED)

				PP = S.get_leftmost_nonterminal()
				for y in generate_language_0(G,S,PP,L):
					y = copy.deepcopy(y)
					parameter_tree.append( y[0] )
				parameter_trees.append(parameter_tree)

				G.set_output_format(output_format)
			elif isinstance(term,Terminal_generator):
				L.log_start(gentree.gen_tree,str(term),S,False)

				for terminal in term.generate():
					terminal = T(terminal)
					L.log_start(gentree.gen_tree,None,\
					 Sentential_form( [[terminal]] ),True)
					parameter_tree.append( [terminal] )
					L.log_end(gentree.gen_tree)
				parameter_trees.append(parameter_tree)

				L.log_end(gentree.gen_tree)
			else:
				L.log_start(gentree.gen_tree,str(term),S,True)

				parameter_tree.append( term )
				parameter_trees.append(parameter_tree)

				L.log_end(gentree.gen_tree)
		L.log_end(gentree.parameter_trees)

		# domain_sizes = sizes of parameter trees in index_set
		domain_sizes = [None] * len(index_set)
		for i in range(len(index_set)):
			domain_sizes[i] = len( parameter_trees[index_set[i]] )

		# cover_function = cov of strength function
		if strength == 1:
			cover_function = covers_hill.gen1Cover
		elif strength == 2:
			cover_function = covers_hill.gen2Cover
			#cover_function = covers_cpp.gen2Cover
		elif strength == 3:
			cover_function = covers_hill.gen3Cover
		else:
			cover_function = covers_hill.genNCover

		# tuple = first string in L(R.rhs)
		tuple = []
		for parameter_tree in parameter_trees:
			tuple.append( parameter_tree[0] )

		for row in cover_function(domain_sizes):
			if prune_tree(GP,PP,L):
				break

			# populate tuple with row values
			for i in range(len(index_set)):
				tuple[index_set[i]] = \
				 parameter_trees[index_set[i]][row[i]]
			yield tuple

def execute_postcode(S,PP):
	'''
	Purpose
		for each rule R in PP whose yield is ground, execute R.postcode
	Precondition
		S: sentential form
		PP: parse tree path
	'''
	R = PP[-1][1]
	rule_yield = S.get(PP)

	while is_ground(rule_yield):
		if R != None:
			R.postcode(rule_yield)
		PP = PP[:-1]

		if len(PP) == 0:
			break

		# R = top rule in PP
		R = PP[-1][1]
		rule_yield = S.get(PP)

def generate_language(G,variable_name):
	'''
	Purpose
		generate L(variable_name) by calling the generate_language_0
		 function.
	Precondition
		G: grammar
		A rule in G has variable_name as the rule's left-hand side.
	'''
	S = Sentential_form( [V(variable_name)] )
	PP = S.get_leftmost_nonterminal()
	L = G.create_gentree()

	for s in generate_language_0(G,S,PP,L):
		if G.output_format != NONE:
			yield str(s)

	L.destructor()

def generate_language_0(G,S,PP,L):
	'''
	Purpose
		generate L(S,PP) and log generation tree using L.
	Precondition
		G: grammar
		S: sentential form
		PP: parse tree path
		L: generation tree object
	'''
	global GP,gentree

	if is_ground(S.contents):
		L.log_start(gentree.gen_tree,str(GP[-1]),S,True)
		yield G.format_output(S)
		L.log_end(gentree.gen_tree)
		return

	# S' = deep copy of S, copy needed for backtracking
	new_S = copy.deepcopy(S)
	# N = non-terminal at PP in S'
	N = new_S.get(PP)

	if isinstance(N,Terminal_generator):
		for terminal in N.generate():
			new_S.replace(PP,[T(terminal)])
			execute_postcode(new_S,PP)
			new_PP = new_S.get_leftmost_nonterminal(PP)
			for y in generate_language_0(G,new_S,new_PP,L):
				yield y
	elif isinstance(N,V):
		if len(GP) > 0:
			if GP[-1].tags.has_key('cov') and \
			 new_S.contents[0] == N:
				id = N
			else:
				id = GP[-1]
		else:
			id = None

		L.log_start(gentree.gen_tree,str(id),S,False)
		for R in G.generate_matching_rules(N):
			GP.append(R)

			# replace top rule in PP by R
			PP[-1][1] = R

			if prune_tree(GP,PP,L):
				GP.pop()
				continue

			if R.tags.has_key('cov'):
				cov_tuples = []
				for C in generate_cov(G,R,PP,L):
					new_S.replace(PP,C)
					execute_postcode(new_S,PP)
					new_PP = \
					 new_S.get_leftmost_nonterminal(PP)
					for y in generate_language_0(G,new_S,\
					 new_PP,L):
						yield y
			else:
				new_S.replace(PP,R.rhs)
				if is_ground(R.rhs):
					execute_postcode(new_S,PP)
				new_PP = new_S.get_leftmost_nonterminal(PP)
				for y in generate_language_0(G,new_S,new_PP,L):
					yield y

			GP.pop()
		L.log_end(gentree.gen_tree)
