from enum import Enum

class LitType(Enum):
	TAGGLOB = 2
	TITLEGLOB = 3
	TAG = 9

class TokType(Enum):
	OR = 0
	NOT = 1
	EOF = 5
	AND = 6
	OPEN = 7
	CLOSE = 8

def classify_head(l):
	if len(l) == 0:
		return (TokType.EOF, None)

	s = l[0]
	if s == "OR":
		return (TokType.OR,None)
	elif s == "NOT":
		return (TokType.NOT,None)
	elif s == "[":
		return (TokType.OPEN,None)
	elif s == "]":
		return (TokType.CLOSE,None)
	elif s[:2] == "~~":
		return (LitType.TAGGLOB, s[2:])
	elif s[:2] == "~-":
		return (LitType.TITLEGLOB, s[2:])
	else:
		return (LitType.TAG, s)

class Atom:
	def __str__(self):
		return f'({self.op} "{self.v}")'
	def __init__(self, op, v):
		self.op = op
		self.v = v

class ParseTree:
	def push(self, pt):
		self.l.append(pt)
	def __str__(self):
		s = f'({self.op}'
		for i in self.l:
			s = s + ' ' + str(i)
		return s + ')'
	def __init__(self, op, l):
		self.op = op
		self.l = l

def query_lit(alist, lit, isNot):
	if lit.op == LitType.TAGGLOB:
		qr = f"""tag in (SELECT id FROM tags
			WHERE name GLOB ?{len(alist)})"""
	elif lit.op == LitType.TITLEGLOB:
		qr = f"""card in (SELECT id FROM cards
			WHERE name GLOB ?{len(alist)})"""
	elif lit.op == LitType.TAG:
		qr = f"""tag in (SELECT id FROM tags
		         WHERE name = ?{len(alist)} LIMIT 1)"""
	else:
		raise ParseError

	alist.append(lit.v)

	if isNot:
		qr = f"NOT ({qr})"
	return f"SELECT card FROM tagmap WHERE {qr}"

# Returns bl,xpr where bl = True when xpr is for a literal
def build(alist, pt):
	if pt.op == TokType.OR:
		conn = "UNION"
	elif pt.op == TokType.AND:
		conn = "INTERSECTION"
	elif pt.op == TokType.NOT:
		return True,query_lit(alist, pt.l[0], True)
	elif pt.op in LitType:
		return True,query_lit(alist, pt, False)
	else:
		raise ParseError

	v, r = build(alist, pt.l[0])
	if not v:
		r = f"SELECT card FROM ({r})"
	for i in pt.l[1:]:
		v,exr = build(alist, i)
		if not v:
			exr = f"SELECT card FROM f({exr})"
		r = f"{r} {conn} {exr}"
	return False,r

def encapsulate(pt, op):
	if pt.op != op:
		pt = ParseTree(op, [pt])
	return pt

def demorgan(pt):
	if pt.op in LitType:
		return ParseTree(TokType.NOT, [pt])
	elif pt.op == TokType.NOT:
		return pt.l[0]
	elif pt.op == TokType.OR:
		pt.op = TokType.AND
	elif pt.op == TokType.AND:
		pt.op = TokType.OR
	else:
		raise ParseError

	pt.l = [demorgan(x) for x in pt.l]
	return pt

"""
The parser is implemented like

e1 ::= e2 ("OR" e2)*;
e2 ::= e3*;
e3 ::= "NOT"? e4;
e4 ::= TAG | "[" e1 "]";
"""

class ParseError(Exception):
	pass

def e4(l):
	typ,s = classify_head(l)

	if typ == TokType.OPEN:
		pt,l = e1(l[1:])
		typ,_ = classify_head(l)
		if typ != TokType.CLOSE:
			raise ParseError
		return pt,l[1:]
	elif typ in LitType:
		return Atom(typ, s), l[1:]
	else:
		raise ParseError

def e3(l):
	typ,_ = classify_head(l)
	if typ == TokType.NOT:
		pt,l = e4(l[1:])
		return demorgan(pt), l
	return e4(l)

def e2(l):
	pt,l = e3(l)
	try:
		while True:
			pt2,l = e3(l)
			pt = encapsulate(pt, TokType.AND)
			pt.push(pt2)
	except ParseError:
		pass
	return pt,l

def e1(l):
	pt,l = e2(l)
	typ,_ = classify_head(l)

	try:
		while typ == TokType.OR:
			pt2,l = e2(l[1:])
			pt = encapsulate(pt, TokType.OR)
			pt.push(pt2)
			typ,_ = classify_head(l)
	except ParseError:
		pass
	return pt,l

def parse(l):
	x,l = e1(l)
	if l != []:
		raise ParseError
	return x