#  Copyright (c) 1998-2000 John Aycock
#  
#  Permission is hereby granted, free of charge, to any person obtaining
#  a copy of this software and associated documentation files (the
#  "Software"), to deal in the Software without restriction, including
#  without limitation the rights to use, copy, modify, merge, publish,
#  distribute, sublicense, and/or sell copies of the Software, and to
#  permit persons to whom the Software is furnished to do so, subject to
#  the following conditions:
#  
#  The above copyright notice and this permission notice shall be
#  included in all copies or substantial portions of the Software.
#  
#  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
#  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
#  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
#  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
#  CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
#  TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
#  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

__version__ = 'SPARK-0.6.1'

import re
import sys
import string

def _namelist(instance):
	namelist, namedict, classlist = [], {}, [instance.__class__]
	for c in classlist:
		for b in c.__bases__:
			classlist.append(b)
		for name in dir(c):
			if not namedict.has_key(name):
				namelist.append(name)
				namedict[name] = 1
	return namelist

class GenericScanner:
	def __init__(self):
		pattern = self.reflect()
		self.re = re.compile(pattern, re.VERBOSE)

		self.index2func = {}
		for name, number in self.re.groupindex.items():
			self.index2func[number-1] = getattr(self, 't_' + name)

	def makeRE(self, name):
		doc = getattr(self, name).__doc__
		rv = '(?P<%s>%s)' % (name[2:], doc)
		return rv

	def reflect(self):
		rv = []
		for name in _namelist(self):
			if name[:2] == 't_' and name != 't_default':
				rv.append(self.makeRE(name))

		rv.append(self.makeRE('t_default'))
		return string.join(rv, '|')

	def error(self, s, pos):
		print "Lexical error at position %s" % pos
		raise SystemExit

	def tokenize(self, s):
		pos = 0
		n = len(s)
		while pos < n:
			m = self.re.match(s, pos)
			if m is None:
				self.error(s, pos)

			groups = m.groups()
			for i in range(len(groups)):
				if groups[i] and self.index2func.has_key(i):
					self.index2func[i](groups[i])
			pos = m.end()

	def t_default(self, s):
		r'( . | \n )+'
		pass

class GenericParser:
	def __init__(self, start):
		self.rules = {}
		self.rule2func = {}
		self.rule2name = {}
		self.collectRules()
		self.startRule = self.augment(start)
		self.ruleschanged = 1

	_START = 'START'
	_EOF = 'EOF'

	#
	#  A hook for GenericASTBuilder and GenericASTMatcher.
	#
	def preprocess(self, rule, func):	return rule, func

	def addRule(self, doc, func):
		rules = string.split(doc)

		index = []
		for i in range(len(rules)):
			if rules[i] == '::=':
				index.append(i-1)
		index.append(len(rules))

		for i in range(len(index)-1):
			lhs = rules[index[i]]
			rhs = rules[index[i]+2:index[i+1]]
			rule = (lhs, tuple(rhs))

			rule, fn = self.preprocess(rule, func)

			if self.rules.has_key(lhs):
				self.rules[lhs].append(rule)
			else:
				self.rules[lhs] = [ rule ]
			self.rule2func[rule] = fn
			self.rule2name[rule] = func.__name__[2:]
		self.ruleschanged = 1

	def collectRules(self):
		for name in _namelist(self):
			if name[:2] == 'p_':
				func = getattr(self, name)
				doc = func.__doc__
				self.addRule(doc, func)

	def augment(self, start):
		#
		#  Tempting though it is, this isn't made into a call
		#  to self.addRule() because the start rule shouldn't
		#  be subject to preprocessing.
		#
		startRule = (self._START, ( start, self._EOF ))
		self.rule2func[startRule] = lambda args: args[0]
		self.rules[self._START] = [ startRule ]
		self.rule2name[startRule] = ''
		return startRule

	def makeFIRST(self):
		union = {}
		self.first = {}
		
		for rulelist in self.rules.values():
			for lhs, rhs in rulelist:
				if not self.first.has_key(lhs):
					self.first[lhs] = {}

				if len(rhs) == 0:
					self.first[lhs][None] = 1
					continue

				sym = rhs[0]
				if not self.rules.has_key(sym):
					self.first[lhs][sym] = 1
				else:
					union[(sym, lhs)] = 1
		changes = 1
		while changes:
			changes = 0
			for src, dest in union.keys():
				destlen = len(self.first[dest])
				self.first[dest].update(self.first[src])
				if len(self.first[dest]) != destlen:
					changes = 1

	#
	#  An Earley parser, as per J. Earley, "An Efficient Context-Free
	#  Parsing Algorithm", CACM 13(2), pp. 94-102.  Also J. C. Earley,
	#  "An Efficient Context-Free Parsing Algorithm", Ph.D. thesis,
	#  Carnegie-Mellon University, August 1968, p. 27.
	#
	
	def typestring(self, token):
		return None

	def error(self, token):
		print "Syntax error at or near `%s' token" % token
		raise SystemExit

	def parse(self, tokens):
		tree = {}
		tokens.append(self._EOF)
		states = { 0: [ (self.startRule, 0, 0) ] }
		
		if self.ruleschanged:
			self.makeFIRST()

		for i in xrange(len(tokens)):
			states[i+1] = []

			if states[i] == []:
				break				
			self.buildState(tokens[i], states, i, tree)

		#_dump(tokens, states)

		if i < len(tokens)-1 or states[i+1] != [(self.startRule, 2, 0)]:
			del tokens[-1]
			self.error(tokens[i-1])
		rv = self.buildTree(tokens, tree, ((self.startRule, 2, 0), i+1))
		del tokens[-1]
		return rv

	def buildState(self, token, states, i, tree):
		needsCompletion = {}
		state = states[i]
		predicted = {}
		
		for item in state:
			rule, pos, parent = item
			lhs, rhs = rule

			#
			#  A -> a . (completer)
			#
			if pos == len(rhs):
				if len(rhs) == 0:
					needsCompletion[lhs] = (item, i)

				for pitem in states[parent]:
					if pitem is item:
						break

					prule, ppos, pparent = pitem
					plhs, prhs = prule

					if prhs[ppos:ppos+1] == (lhs,):
						new = (prule,
						       ppos+1,
						       pparent)
						if new not in state:
							state.append(new)
							tree[(new, i)] = [(item, i)]
						else:
							tree[(new, i)].append((item, i))
				continue

			nextSym = rhs[pos]

			#
			#  A -> a . B (predictor)
			#
			if self.rules.has_key(nextSym):
				#
				#  Work on completer step some more; for rules
				#  with empty RHS, the "parent state" is the
				#  current state we're adding Earley items to,
				#  so the Earley items the completer step needs
				#  may not all be present when it runs.
				#
				if needsCompletion.has_key(nextSym):
					new = (rule, pos+1, parent)
					olditem_i = needsCompletion[nextSym]
					if new not in state:
						state.append(new)
						tree[(new, i)] = [olditem_i]
					else:
						tree[(new, i)].append(olditem_i)

				#
				#  Has this been predicted already?
				#
				if predicted.has_key(nextSym):
					continue
				predicted[nextSym] = 1

				ttype = token is not self._EOF and \
					self.typestring(token) or \
					None
				if ttype is not None:
					#
					#  Even smarter predictor, when the
					#  token's type is known.  The code is
					#  grungy, but runs pretty fast.  Three
					#  cases are looked for: rules with
					#  empty RHS; first symbol on RHS is a
					#  terminal; first symbol on RHS is a
					#  nonterminal (and isn't nullable).
					#
					for prule in self.rules[nextSym]:
						new = (prule, 0, i)
						prhs = prule[1]
						if len(prhs) == 0:
							state.append(new)
							continue
						prhs0 = prhs[0]
						if not self.rules.has_key(prhs0):
							if prhs0 != ttype:
								continue
							else:
								state.append(new)
								continue
						first = self.first[prhs0]
						if not first.has_key(None) and \
						   not first.has_key(ttype):
							continue
						state.append(new)
					continue

				for prule in self.rules[nextSym]:
					#
					#  Smarter predictor, as per Grune &
					#  Jacobs' _Parsing Techniques_.  Not
					#  as good as FIRST sets though.
					#
					prhs = prule[1]
					if len(prhs) > 0 and \
					   not self.rules.has_key(prhs[0]) and \
					   token != prhs[0]:
						continue
					state.append((prule, 0, i))

			#
			#  A -> a . c (scanner)
			#
			elif token == nextSym:
				#assert new not in states[i+1]
				states[i+1].append((rule, pos+1, parent))

	def buildTree(self, tokens, tree, root):
		stack = []
		self.buildTree_r(stack, tokens, -1, tree, root)
		return stack[0]

	def buildTree_r(self, stack, tokens, tokpos, tree, root):
		(rule, pos, parent), state = root
		
		while pos > 0:
			want = ((rule, pos, parent), state)
			if not tree.has_key(want):
				#
				#  Since pos > 0, it didn't come from closure,
				#  and if it isn't in tree[], then there must
				#  be a terminal symbol to the left of the dot.
				#  (It must be from a "scanner" step.)
				#
				pos = pos - 1
				state = state - 1
				stack.insert(0, tokens[tokpos])
				tokpos = tokpos - 1
			else:
				#
				#  There's a NT to the left of the dot.
				#  Follow the tree pointer recursively (>1
				#  tree pointers from it indicates ambiguity).
				#  Since the item must have come about from a
				#  "completer" step, the state where the item
				#  came from must be the parent state of the
				#  item the tree pointer points to.
				#
				children = tree[want]
				if len(children) > 1:
					child = self.ambiguity(children)
				else:
					child = children[0]
				
				tokpos = self.buildTree_r(stack,
							  tokens, tokpos,
							  tree, child)
				pos = pos - 1
				(crule, cpos, cparent), cstate = child
				state = cparent
				
		lhs, rhs = rule
		result = self.rule2func[rule](stack[:len(rhs)])
		stack[:len(rhs)] = [result]
		return tokpos

	def ambiguity(self, children):
		#
		#  XXX - problem here and in collectRules() if the same
		#	 rule appears in >1 method.  But in that case the
		#	 user probably gets what they deserve :-)  Also
		#	 undefined results if rules causing the ambiguity
		#	 appear in the same method.
		#
		sortlist = []
		name2index = {}
		for i in range(len(children)):
			((rule, pos, parent), index) = children[i]
			lhs, rhs = rule
			name = self.rule2name[rule]
			sortlist.append((len(rhs), name))
			name2index[name] = i
		sortlist.sort()
		list = map(lambda (a,b): b, sortlist)
		return children[name2index[self.resolve(list)]]

	def resolve(self, list):
		#
		#  Resolve ambiguity in favor of the shortest RHS.
		#  Since we walk the tree from the top down, this
		#  should effectively resolve in favor of a "shift".
		#
		return list[0]

#
#  GenericASTBuilder automagically constructs a concrete/abstract syntax tree
#  for a given input.  The extra argument is a class (not an instance!)
#  which supports the "__setslice__" and "__len__" methods.
#
#  XXX - silently overrides any user code in methods.
#

class GenericASTBuilder(GenericParser):
	def __init__(self, AST, start):
		GenericParser.__init__(self, start)
		self.AST = AST

	def preprocess(self, rule, func):
		rebind = lambda lhs, self=self: \
				lambda args, lhs=lhs, self=self: \
					self.buildASTNode(args, lhs)
		lhs, rhs = rule
		return rule, rebind(lhs)

	def buildASTNode(self, args, lhs):
		children = []
		for arg in args:
			if isinstance(arg, self.AST):
				children.append(arg)
			else:
				children.append(self.terminal(arg))
		return self.nonterminal(lhs, children)

	def terminal(self, token):	return token

	def nonterminal(self, type, args):
		rv = self.AST(type)
		rv[:len(args)] = args
		return rv

#
#  GenericASTTraversal is a Visitor pattern according to Design Patterns.  For
#  each node it attempts to invoke the method n_<node type>, falling
#  back onto the default() method if the n_* can't be found.  The preorder
#  traversal also looks for an exit hook named n_<node type>_exit (no default
#  routine is called if it's not found).  To prematurely halt traversal
#  of a subtree, call the prune() method -- this only makes sense for a
#  preorder traversal.  Node type is determined via the typestring() method.
#

class GenericASTTraversalPruningException:
	pass

class GenericASTTraversal:
	def __init__(self, ast):
		self.ast = ast

	def typestring(self, node):
		return node.type

	def prune(self):
		raise GenericASTTraversalPruningException

	def preorder(self, node=None):
		if node is None:
			node = self.ast

		try:
			name = 'n_' + self.typestring(node)
			if hasattr(self, name):
				func = getattr(self, name)
				func(node)
			else:
				self.default(node)
		except GenericASTTraversalPruningException:
			return

		for kid in node:
			self.preorder(kid)

		name = name + '_exit'
		if hasattr(self, name):
			func = getattr(self, name)
			func(node)

	def postorder(self, node=None):
		if node is None:
			node = self.ast

		for kid in node:
			self.postorder(kid)

		name = 'n_' + self.typestring(node)
		if hasattr(self, name):
			func = getattr(self, name)
			func(node)
		else:
			self.default(node)


	def default(self, node):
		pass

#
#  GenericASTMatcher.  AST nodes must have "__getitem__" and "__cmp__"
#  implemented.
#
#  XXX - makes assumptions about how GenericParser walks the parse tree.
#

class GenericASTMatcher(GenericParser):
	def __init__(self, start, ast):
		GenericParser.__init__(self, start)
		self.ast = ast

	def preprocess(self, rule, func):
		rebind = lambda func, self=self: \
				lambda args, func=func, self=self: \
					self.foundMatch(args, func)
		lhs, rhs = rule
		rhslist = list(rhs)
		rhslist.reverse()

		return (lhs, tuple(rhslist)), rebind(func)

	def foundMatch(self, args, func):
		func(args[-1])
		return args[-1]

	def match_r(self, node):
		self.input.insert(0, node)
		children = 0

		for child in node:
			if children == 0:
				self.input.insert(0, '(')
			children = children + 1
			self.match_r(child)

		if children > 0:
			self.input.insert(0, ')')

	def match(self, ast=None):
		if ast is None:
			ast = self.ast
		self.input = []

		self.match_r(ast)
		self.parse(self.input)

	def resolve(self, list):
		#
		#  Resolve ambiguity in favor of the longest RHS.
		#
		return list[-1]

def _dump(tokens, states):
	for i in range(len(states)):
		print 'state', i
		for (lhs, rhs), pos, parent in states[i]:
			print '\t', lhs, '::=',
			print string.join(rhs[:pos]),
			print '.',
			print string.join(rhs[pos:]),
			print ',', parent
		if i < len(tokens):
			print
			print 'token', str(tokens[i])
			print