queryparse: add function to build SQL queries

SQLite allows for UNIONs and INTERSECTIONs between SELECT statements,
but it does not support grouping them. By recursively applying DeMorgan's
laws, the parser can reduce the parse tree to only

* Literals
* NOT literals (i.e. "all items not belonging to this tag")
* ANDs
* ORs

What SQLite /can/ do is have SELECT statements come from other SELECT
statements. A query like (X & Y & Z) | (A & B & C) in pseudo-SQLite
becomes

    SELECT * FROM (
     SELECT * FROM tbl WHERE name IN X
     INTERSECTION
     SELECT * FROM tbl WHERE name IN Y
     INTERSECTION
     SELECT * FROM tbl WHERE name IN Z
    )
    UNION
    SELECT * FROM (
     SELECT * FROM tbl WHERE name IN A
     INTERSECTION
     SELECT * FROM tbl WHERE name IN B
     INTERSECTION
     SELECT * FROM tbl WHERE name IN C
    )

One future optimization would be to group all literals at a certain
level with each other, so that there are less direct queries to the
entire tag table.

2 files changed, 73 insertions, 1 deletions

diff --git a/queryparse.py b/queryparse.py
index 3377803..44a42dd 100644
--- a/queryparse.py
+++ b/queryparse.py
@@ -52,6 +52,48 @@ class ParseTree:
 		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])
diff --git a/test/t_queryparse.py b/test/t_queryparse.py
index 3cf5dcb..ea15c42 100755
--- a/test/t_queryparse.py
+++ b/test/t_queryparse.py
@@ -3,11 +3,41 @@ import sys
 sys.path.insert(0, "../")
 import queryparse
 
+def prettyprint(s):
+	ind = 0
+	start = True
+	for i in s:
+		if i == "\n":
+			if not start:
+				print(" ", end="")
+			start = True
+			continue
+		if (i == " " or i == "\t") and start:
+			continue
+		start = False
+		if i == "(":
+			ind = ind + 1
+			print()
+			for j in range(0,ind):
+				print(" ", end="")
+			start = False
+			print("(", end="")
+		elif i == ")":
+			print(")")
+			ind = ind - 1
+			for j in range(0, ind):
+				print(" ", end="")
+			start = True
+		else:
+			print(i, end="")
+
 def f(x):
 	print(x)
 	v,lits = queryparse.parse(x)
-	print(v)
+	prettyprint(str(v))
 	print(lits)
+	_,exr = queryparse.build([], v)
+	prettyprint(exr)
 	print()
 
 f(["x", "OR", "y"])