"""
Converting the 'parse-tree' output of pyparsing to a SPARQL Algebra expression

http://www.w3.org/TR/sparql11-query/#sparqlQuery

"""

import collections
import functools
import operator
import typing
from functools import reduce
from typing import (
    Any,
    Callable,
    DefaultDict,
    Dict,
    Iterable,
    List,
    Mapping,
    Optional,
    Set,
    Tuple,
    overload,
)

from pyparsing import ParseResults

from rdflib.paths import (
    AlternativePath,
    InvPath,
    MulPath,
    NegatedPath,
    Path,
    SequencePath,
)
from rdflib.plugins.sparql.operators import TrueFilter, and_
from rdflib.plugins.sparql.operators import simplify as simplifyFilters
from rdflib.plugins.sparql.parserutils import CompValue, Expr
from rdflib.plugins.sparql.sparql import Prologue, Query, Update

# ---------------------------
# Some convenience methods
from rdflib.term import BNode, Identifier, Literal, URIRef, Variable


def OrderBy(p: CompValue, expr: List[CompValue]) -> CompValue:
    return CompValue("OrderBy", p=p, expr=expr)


def ToMultiSet(
    p: typing.Union[List[Dict[Variable, Identifier]], CompValue]
) -> CompValue:
    return CompValue("ToMultiSet", p=p)


def Union(p1: CompValue, p2: CompValue) -> CompValue:
    return CompValue("Union", p1=p1, p2=p2)


def Join(p1: CompValue, p2: Optional[CompValue]) -> CompValue:
    return CompValue("Join", p1=p1, p2=p2)


def Minus(p1: CompValue, p2: CompValue) -> CompValue:
    return CompValue("Minus", p1=p1, p2=p2)


def Graph(term, graph) -> CompValue:
    return CompValue("Graph", term=term, p=graph)


def BGP(triples=None) -> CompValue:
    return CompValue("BGP", triples=triples or [])


def LeftJoin(p1: CompValue, p2: CompValue, expr) -> CompValue:
    return CompValue("LeftJoin", p1=p1, p2=p2, expr=expr)


def Filter(expr, p: CompValue) -> CompValue:
    return CompValue("Filter", expr=expr, p=p)


def Extend(p: CompValue, expr, var) -> CompValue:
    return CompValue("Extend", p=p, expr=expr, var=var)


def Values(res) -> CompValue:
    return CompValue("values", res=res)


def Project(p: CompValue, PV) -> CompValue:
    return CompValue("Project", p=p, PV=PV)


def Group(p: CompValue, expr: Optional[List[Variable]] = None) -> CompValue:
    return CompValue("Group", p=p, expr=expr)


def _knownTerms(
    triple: Tuple[Identifier, Identifier, Identifier],
    varsknown: Set[typing.Union[BNode, Variable]],
    varscount: Dict[Identifier, int],
):
    return (
        len(
            [
                x
                for x in triple
                if x not in varsknown and isinstance(x, (Variable, BNode))
            ]
        ),
        -sum(varscount.get(x, 0) for x in triple),
        not isinstance(triple[2], Literal),
    )


def reorderTriples(
    l_: Iterable[Tuple[Identifier, Identifier, Identifier]]
) -> List[Tuple[Identifier, Identifier, Identifier]]:
    """
    Reorder triple patterns so that we execute the
    ones with most bindings first
    """

    def _addvar(term, varsknown):
        if isinstance(term, (Variable, BNode)):
            varsknown.add(term)

    # NOTE on type errors: most of these are because the same variable is used
    # for different types.

    # type error: List comprehension has incompatible type List[Tuple[None, Tuple[Identifier, Identifier, Identifier]]]; expected List[Tuple[Identifier, Identifier, Identifier]]
    l_ = [(None, x) for x in l_]  # type: ignore[misc]
    varsknown: Set[typing.Union[BNode, Variable]] = set()
    varscount: Dict[Identifier, int] = collections.defaultdict(int)
    for t in l_:
        for c in t[1]:
            if isinstance(c, (Variable, BNode)):
                varscount[c] += 1
    i = 0

    # Done in steps, sort by number of bound terms
    # the top block of patterns with the most bound terms is kept
    # the rest is resorted based on the vars bound after the first
    # block is evaluated

    # we sort by decorate/undecorate, since we need the value of the sort keys

    while i < len(l_):
        # type error: Generator has incompatible item type "Tuple[Any, Identifier]"; expected "Tuple[Identifier, Identifier, Identifier]"
        # type error: Argument 1 to "_knownTerms" has incompatible type "Identifier"; expected "Tuple[Identifier, Identifier, Identifier]"
        l_[i:] = sorted((_knownTerms(x[1], varsknown, varscount), x[1]) for x in l_[i:])  # type: ignore[misc,arg-type]
        # type error: Incompatible types in assignment (expression has type "str", variable has type "Tuple[Identifier, Identifier, Identifier]")
        t = l_[i][0][0]  # type: ignore[assignment] # top block has this many terms bound
        j = 0
        while i + j < len(l_) and l_[i + j][0][0] == t:
            for c in l_[i + j][1]:
                _addvar(c, varsknown)
            j += 1
        i += 1

    # type error: List comprehension has incompatible type List[Identifier]; expected List[Tuple[Identifier, Identifier, Identifier]]
    return [x[1] for x in l_]  # type: ignore[misc]


def triples(
    l: typing.Union[  # noqa: E741
        List[List[Identifier]], List[Tuple[Identifier, Identifier, Identifier]]
    ]
) -> List[Tuple[Identifier, Identifier, Identifier]]:
    # NOTE on type errors: errors are a result of the variable being reused for
    # a different type.
    # type error: Incompatible types in assignment (expression has type "Sequence[Identifier]", variable has type "Union[List[List[Identifier]], List[Tuple[Identifier, Identifier, Identifier]]]")
    l = reduce(lambda x, y: x + y, l)  # type: ignore[assignment]  # noqa: E741
    if (len(l) % 3) != 0:
        raise Exception("these aint triples")
    # type error: Generator has incompatible item type "Tuple[Union[List[Identifier], Tuple[Identifier, Identifier, Identifier]], Union[List[Identifier], Tuple[Identifier, Identifier, Identifier]], Union[List[Identifier], Tuple[Identifier, Identifier, Identifier]]]"; expected "Tuple[Identifier, Identifier, Identifier]"
    return reorderTriples((l[x], l[x + 1], l[x + 2]) for x in range(0, len(l), 3))  # type: ignore[misc]


def translatePName(p: typing.Union[CompValue, str], prologue: Prologue):
    """
    Expand prefixed/relative URIs
    """
    if isinstance(p, CompValue):
        if p.name == "pname":
            return prologue.absolutize(p)
        if p.name == "literal":
            # type error: Argument "datatype" to "Literal" has incompatible type "Union[CompValue, str, None]"; expected "Optional[str]"
            return Literal(
                p.string, lang=p.lang, datatype=prologue.absolutize(p.datatype)  # type: ignore[arg-type]
            )
    elif isinstance(p, URIRef):
        return prologue.absolutize(p)


@overload
def translatePath(p: URIRef) -> None:
    ...


@overload
def translatePath(p: CompValue) -> "Path":
    ...


# type error: Missing return statement
def translatePath(p: typing.Union[CompValue, URIRef]) -> Optional["Path"]:  # type: ignore[return]
    """
    Translate PropertyPath expressions
    """

    if isinstance(p, CompValue):
        if p.name == "PathAlternative":
            if len(p.part) == 1:
                return p.part[0]
            else:
                return AlternativePath(*p.part)

        elif p.name == "PathSequence":
            if len(p.part) == 1:
                return p.part[0]
            else:
                return SequencePath(*p.part)

        elif p.name == "PathElt":
            if not p.mod:
                return p.part
            else:
                if isinstance(p.part, list):
                    if len(p.part) != 1:
                        raise Exception("Denkfehler!")

                    return MulPath(p.part[0], p.mod)
                else:
                    return MulPath(p.part, p.mod)

        elif p.name == "PathEltOrInverse":
            if isinstance(p.part, list):
                if len(p.part) != 1:
                    raise Exception("Denkfehler!")
                return InvPath(p.part[0])
            else:
                return InvPath(p.part)

        elif p.name == "PathNegatedPropertySet":
            if isinstance(p.part, list):
                return NegatedPath(AlternativePath(*p.part))
            else:
                return NegatedPath(p.part)


def translateExists(
    e: typing.Union[Expr, Literal, Variable]
) -> typing.Union[Expr, Literal, Variable]:
    """
    Translate the graph pattern used by EXISTS and NOT EXISTS
    http://www.w3.org/TR/sparql11-query/#sparqlCollectFilters
    """

    def _c(n):
        if isinstance(n, CompValue):
            if n.name in ("Builtin_EXISTS", "Builtin_NOTEXISTS"):
                n.graph = translateGroupGraphPattern(n.graph)
                if n.graph.name == "Filter":
                    # filters inside (NOT) EXISTS can see vars bound outside
                    n.graph.no_isolated_scope = True

    e = traverse(e, visitPost=_c)

    return e


def collectAndRemoveFilters(parts):
    """

    FILTER expressions apply to the whole group graph pattern in which
    they appear.

    http://www.w3.org/TR/sparql11-query/#sparqlCollectFilters
    """

    filters = []

    i = 0
    while i < len(parts):
        p = parts[i]
        if p.name == "Filter":
            filters.append(translateExists(p.expr))
            parts.pop(i)
        else:
            i += 1

    if filters:
        return and_(*filters)

    return None


def translateGroupOrUnionGraphPattern(graphPattern: CompValue) -> Optional[CompValue]:
    A: Optional[CompValue] = None

    for g in graphPattern.graph:
        g = translateGroupGraphPattern(g)
        if not A:
            A = g
        else:
            A = Union(A, g)
    return A


def translateGraphGraphPattern(graphPattern: CompValue) -> CompValue:
    return Graph(graphPattern.term, translateGroupGraphPattern(graphPattern.graph))


def translateInlineData(graphPattern: CompValue) -> CompValue:
    return ToMultiSet(translateValues(graphPattern))


def translateGroupGraphPattern(graphPattern: CompValue) -> CompValue:
    """
    http://www.w3.org/TR/sparql11-query/#convertGraphPattern
    """

    if graphPattern.name == "SubSelect":
        return ToMultiSet(translate(graphPattern)[0])

    if not graphPattern.part:
        graphPattern.part = []  # empty { }

    filters = collectAndRemoveFilters(graphPattern.part)

    g: List[CompValue] = []
    for p in graphPattern.part:
        if p.name == "TriplesBlock":
            # merge adjacent TripleBlocks
            if not (g and g[-1].name == "BGP"):
                g.append(BGP())
            g[-1]["triples"] += triples(p.triples)
        else:
            g.append(p)

    G = BGP()
    for p in g:
        if p.name == "OptionalGraphPattern":
            A = translateGroupGraphPattern(p.graph)
            if A.name == "Filter":
                G = LeftJoin(G, A.p, A.expr)
            else:
                G = LeftJoin(G, A, TrueFilter)
        elif p.name == "MinusGraphPattern":
            G = Minus(p1=G, p2=translateGroupGraphPattern(p.graph))
        elif p.name == "GroupOrUnionGraphPattern":
            G = Join(p1=G, p2=translateGroupOrUnionGraphPattern(p))
        elif p.name == "GraphGraphPattern":
            G = Join(p1=G, p2=translateGraphGraphPattern(p))
        elif p.name == "InlineData":
            G = Join(p1=G, p2=translateInlineData(p))
        elif p.name == "ServiceGraphPattern":
            G = Join(p1=G, p2=p)
        elif p.name in ("BGP", "Extend"):
            G = Join(p1=G, p2=p)
        elif p.name == "Bind":
            # translateExists will translate the expression if it is EXISTS, and otherwise return
            # the expression as is. This is needed because EXISTS has a graph pattern
            # which must be translated to work properly during evaluation.
            G = Extend(G, translateExists(p.expr), p.var)

        else:
            raise Exception(
                "Unknown part in GroupGraphPattern: %s - %s" % (type(p), p.name)
            )

    if filters:
        G = Filter(expr=filters, p=G)

    return G


class StopTraversal(Exception):  # noqa: N818
    def __init__(self, rv):
        self.rv = rv


def _traverse(
    e: Any,
    visitPre: Callable[[Any], Any] = lambda n: None,
    visitPost: Callable[[Any], Any] = lambda n: None,
):
    """
    Traverse a parse-tree, visit each node

    if visit functions return a value, replace current node
    """
    _e = visitPre(e)
    if _e is not None:
        return _e

    if e is None:
        return None

    if isinstance(e, (list, ParseResults)):
        return [_traverse(x, visitPre, visitPost) for x in e]
    # type error: Statement is unreachable
    elif isinstance(e, tuple):  # type: ignore[unreachable]
        return tuple([_traverse(x, visitPre, visitPost) for x in e])

    elif isinstance(e, CompValue):
        for k, val in e.items():
            e[k] = _traverse(val, visitPre, visitPost)

    # type error: Statement is unreachable
    _e = visitPost(e)  # type: ignore[unreachable]
    if _e is not None:
        return _e

    return e


def _traverseAgg(e, visitor: Callable[[Any, Any], Any] = lambda n, v: None):
    """
    Traverse a parse-tree, visit each node

    if visit functions return a value, replace current node
    """

    res = []

    if isinstance(e, (list, ParseResults, tuple)):
        res = [_traverseAgg(x, visitor) for x in e]
    # type error: Statement is unreachable
    elif isinstance(e, CompValue):  # type: ignore[unreachable]
        for k, val in e.items():
            if val is not None:
                res.append(_traverseAgg(val, visitor))

    return visitor(e, res)


def traverse(
    tree,
    visitPre: Callable[[Any], Any] = lambda n: None,
    visitPost: Callable[[Any], Any] = lambda n: None,
    complete: Optional[bool] = None,
):
    """
    Traverse tree, visit each node with visit function
    visit function may raise StopTraversal to stop traversal
    if complete!=None, it is returned on complete traversal,
    otherwise the transformed tree is returned
    """
    try:
        r = _traverse(tree, visitPre, visitPost)
        if complete is not None:
            return complete
        return r
    except StopTraversal as st:
        return st.rv


def _hasAggregate(x) -> None:
    """
    Traverse parse(sub)Tree
    return true if any aggregates are used
    """

    if isinstance(x, CompValue):
        if x.name.startswith("Aggregate_"):
            raise StopTraversal(True)


# type error: Missing return statement
def _aggs(e, A) -> Optional[Variable]:  # type: ignore[return]
    """
    Collect Aggregates in A
    replaces aggregates with variable references
    """

    # TODO: nested Aggregates?

    if isinstance(e, CompValue) and e.name.startswith("Aggregate_"):
        A.append(e)
        aggvar = Variable("__agg_%d__" % len(A))
        e["res"] = aggvar
        return aggvar


# type error: Missing return statement
def _findVars(x, res: Set[Variable]) -> Optional[CompValue]:  # type: ignore[return]
    """
    Find all variables in a tree
    """
    if isinstance(x, Variable):
        res.add(x)
    if isinstance(x, CompValue):
        if x.name == "Bind":
            res.add(x.var)
            return x  # stop recursion and finding vars in the expr
        elif x.name == "SubSelect":
            if x.projection:
                res.update(v.var or v.evar for v in x.projection)
            return x


def _addVars(x, children) -> Set[Variable]:
    """
    find which variables may be bound by this part of the query
    """
    if isinstance(x, Variable):
        return set([x])
    elif isinstance(x, CompValue):
        if x.name == "RelationalExpression":
            x["_vars"] = set()
        elif x.name == "Extend":
            # vars only used in the expr for a bind should not be included
            x["_vars"] = reduce(
                operator.or_,
                [child for child, part in zip(children, x) if part != "expr"],
                set(),
            )

        else:
            x["_vars"] = set(reduce(operator.or_, children, set()))

            if x.name == "SubSelect":
                if x.projection:
                    s = set(v.var or v.evar for v in x.projection)
                else:
                    s = set()

                return s

        return x["_vars"]

    return reduce(operator.or_, children, set())


# type error: Missing return statement
def _sample(e: typing.Union[CompValue, List[Expr], Expr, List[str], Variable], v: Optional[Variable] = None) -> Optional[CompValue]:  # type: ignore[return]
    """
    For each unaggregated variable V in expr
    Replace V with Sample(V)
    """
    if isinstance(e, CompValue) and e.name.startswith("Aggregate_"):
        return e  # do not replace vars in aggregates
    if isinstance(e, Variable) and v != e:
        return CompValue("Aggregate_Sample", vars=e)


def _simplifyFilters(e):
    if isinstance(e, Expr):
        return simplifyFilters(e)


def translateAggregates(
    q: CompValue, M: CompValue
) -> Tuple[CompValue, List[Tuple[Variable, Variable]]]:
    E: List[Tuple[Variable, Variable]] = []
    A: List[CompValue] = []

    # collect/replace aggs in :
    #    select expr as ?var
    if q.projection:
        for v in q.projection:
            if v.evar:
                v.expr = traverse(v.expr, functools.partial(_sample, v=v.evar))
                v.expr = traverse(v.expr, functools.partial(_aggs, A=A))

    # having clause
    if traverse(q.having, _hasAggregate, complete=True):
        q.having = traverse(q.having, _sample)
        traverse(q.having, functools.partial(_aggs, A=A))

    # order by
    if traverse(q.orderby, _hasAggregate, complete=False):
        q.orderby = traverse(q.orderby, _sample)
        traverse(q.orderby, functools.partial(_aggs, A=A))

    # sample all other select vars
    # TODO: only allowed for vars in group-by?
    if q.projection:
        for v in q.projection:
            if v.var:
                rv = Variable("__agg_%d__" % (len(A) + 1))
                A.append(CompValue("Aggregate_Sample", vars=v.var, res=rv))
                E.append((rv, v.var))

    return CompValue("AggregateJoin", A=A, p=M), E


def translateValues(
    v: CompValue,
) -> typing.Union[List[Dict[Variable, Identifier]], CompValue]:
    # if len(v.var)!=len(v.value):
    #     raise Exception("Unmatched vars and values in ValueClause: "+str(v))

    res: List[Dict[Variable, Identifier]] = []
    if not v.var:
        return res
    if not v.value:
        return res
    if not isinstance(v.value[0], list):

        for val in v.value:
            res.append({v.var[0]: val})
    else:
        for vals in v.value:
            res.append(dict(zip(v.var, vals)))

    return Values(res)


def translate(q: CompValue) -> Tuple[CompValue, List[Variable]]:
    """
    http://www.w3.org/TR/sparql11-query/#convertSolMod

    """

    _traverse(q, _simplifyFilters)

    q.where = traverse(q.where, visitPost=translatePath)

    # TODO: Var scope test
    VS: Set[Variable] = set()
    traverse(q.where, functools.partial(_findVars, res=VS))

    # all query types have a where part
    M = translateGroupGraphPattern(q.where)

    aggregate = False
    if q.groupby:
        conditions = []
        # convert "GROUP BY (?expr as ?var)" to an Extend
        for c in q.groupby.condition:
            if isinstance(c, CompValue) and c.name == "GroupAs":
                M = Extend(M, c.expr, c.var)
                c = c.var
            conditions.append(c)

        M = Group(p=M, expr=conditions)
        aggregate = True
    elif (
        traverse(q.having, _hasAggregate, complete=False)
        or traverse(q.orderby, _hasAggregate, complete=False)
        or any(
            traverse(x.expr, _hasAggregate, complete=False)
            for x in q.projection or []
            if x.evar
        )
    ):
        # if any aggregate is used, implicit group by
        M = Group(p=M)
        aggregate = True

    if aggregate:
        M, E = translateAggregates(q, M)
    else:
        E = []

    # HAVING
    if q.having:
        M = Filter(expr=and_(*q.having.condition), p=M)

    # VALUES
    if q.valuesClause:
        M = Join(p1=M, p2=ToMultiSet(translateValues(q.valuesClause)))

    if not q.projection:
        # select *
        PV = list(VS)
    else:
        PV = list()
        for v in q.projection:
            if v.var:
                if v not in PV:
                    PV.append(v.var)
            elif v.evar:
                if v not in PV:
                    PV.append(v.evar)

                E.append((v.expr, v.evar))
            else:
                raise Exception("I expected a var or evar here!")

    for e, v in E:
        M = Extend(M, e, v)

    # ORDER BY
    if q.orderby:
        M = OrderBy(
            M,
            [
                CompValue("OrderCondition", expr=c.expr, order=c.order)
                for c in q.orderby.condition
            ],
        )

    # PROJECT
    M = Project(M, PV)

    if q.modifier:
        if q.modifier == "DISTINCT":
            M = CompValue("Distinct", p=M)
        elif q.modifier == "REDUCED":
            M = CompValue("Reduced", p=M)

    if q.limitoffset:
        offset = 0
        if q.limitoffset.offset is not None:
            offset = q.limitoffset.offset.toPython()

        if q.limitoffset.limit is not None:
            M = CompValue(
                "Slice", p=M, start=offset, length=q.limitoffset.limit.toPython()
            )
        else:
            M = CompValue("Slice", p=M, start=offset)

    return M, PV


# type error: Missing return statement
def simplify(n) -> Optional[CompValue]:  # type: ignore[return]
    """Remove joins to empty BGPs"""
    if isinstance(n, CompValue):
        if n.name == "Join":
            if n.p1.name == "BGP" and len(n.p1.triples) == 0:
                return n.p2
            if n.p2.name == "BGP" and len(n.p2.triples) == 0:
                return n.p1
        elif n.name == "BGP":
            n["triples"] = reorderTriples(n.triples)
            return n


def analyse(n, children):
    """
    Some things can be lazily joined.
    This propegates whether they can up the tree
    and sets lazy flags for all joins
    """

    if isinstance(n, CompValue):
        if n.name == "Join":
            n["lazy"] = all(children)
            return False
        elif n.name in ("Slice", "Distinct"):
            return False
        else:
            return all(children)
    else:
        return True


def translatePrologue(
    p: ParseResults,
    base: Optional[str],
    initNs: Optional[Mapping[str, str]] = None,
    prologue: Optional[Prologue] = None,
) -> Prologue:

    if prologue is None:
        prologue = Prologue()
        prologue.base = ""
    if base:
        prologue.base = base
    if initNs:
        for k, v in initNs.items():
            prologue.bind(k, v)

    x: CompValue
    for x in p:
        if x.name == "Base":
            prologue.base = x.iri
        elif x.name == "PrefixDecl":
            prologue.bind(x.prefix, prologue.absolutize(x.iri))

    return prologue


def translateQuads(quads: CompValue):
    if quads.triples:
        alltriples = triples(quads.triples)
    else:
        alltriples = []

    allquads: DefaultDict[
        str, List[Tuple[Identifier, Identifier, Identifier]]
    ] = collections.defaultdict(list)

    if quads.quadsNotTriples:
        for q in quads.quadsNotTriples:
            if q.triples:
                allquads[q.term] += triples(q.triples)

    return alltriples, allquads


def translateUpdate1(u: CompValue, prologue: Prologue) -> CompValue:
    if u.name in ("Load", "Clear", "Drop", "Create"):
        pass  # no translation needed
    elif u.name in ("Add", "Move", "Copy"):
        pass
    elif u.name in ("InsertData", "DeleteData", "DeleteWhere"):
        t, q = translateQuads(u.quads)
        u["quads"] = q
        u["triples"] = t
        if u.name in ("DeleteWhere", "DeleteData"):
            pass  # TODO: check for bnodes in triples
    elif u.name == "Modify":
        if u.delete:
            u.delete["triples"], u.delete["quads"] = translateQuads(u.delete.quads)
        if u.insert:
            u.insert["triples"], u.insert["quads"] = translateQuads(u.insert.quads)
        u["where"] = translateGroupGraphPattern(u.where)
    else:
        raise Exception("Unknown type of update operation: %s" % u)

    u.prologue = prologue
    return u


def translateUpdate(
    q: CompValue,
    base: Optional[str] = None,
    initNs: Optional[Mapping[str, str]] = None,
) -> Update:
    """
    Returns a list of SPARQL Update Algebra expressions
    """

    res: List[CompValue] = []
    prologue = None
    if not q.request:
        # type error: Incompatible return value type (got "List[CompValue]", expected "Update")
        return res  # type: ignore[return-value]
    for p, u in zip(q.prologue, q.request):
        prologue = translatePrologue(p, base, initNs, prologue)

        # absolutize/resolve prefixes
        u = traverse(u, visitPost=functools.partial(translatePName, prologue=prologue))
        u = _traverse(u, _simplifyFilters)

        u = traverse(u, visitPost=translatePath)

        res.append(translateUpdate1(u, prologue))

    # type error: Argument 1 to "Update" has incompatible type "Optional[Any]"; expected "Prologue"
    return Update(prologue, res)  # type: ignore[arg-type]


def translateQuery(
    q: ParseResults,
    base: Optional[str] = None,
    initNs: Optional[Mapping[str, str]] = None,
) -> Query:
    """
    Translate a query-parsetree to a SPARQL Algebra Expression

    Return a rdflib.plugins.sparql.sparql.Query object
    """

    # We get in: (prologue, query)

    prologue = translatePrologue(q[0], base, initNs)

    # absolutize/resolve prefixes
    q[1] = traverse(
        q[1], visitPost=functools.partial(translatePName, prologue=prologue)
    )

    P, PV = translate(q[1])
    datasetClause = q[1].datasetClause
    if q[1].name == "ConstructQuery":

        template = triples(q[1].template) if q[1].template else None

        res = CompValue(q[1].name, p=P, template=template, datasetClause=datasetClause)
    else:
        res = CompValue(q[1].name, p=P, datasetClause=datasetClause, PV=PV)

    res = traverse(res, visitPost=simplify)
    _traverseAgg(res, visitor=analyse)
    _traverseAgg(res, _addVars)

    return Query(prologue, res)


class ExpressionNotCoveredException(Exception):  # noqa: N818
    pass


def translateAlgebra(query_algebra: Query) -> str:
    """

    :param query_algebra: An algebra returned by the function call algebra.translateQuery(parse_tree).
    :return: The query form generated from the SPARQL 1.1 algebra tree for select queries.

    """
    import os

    def overwrite(text):
        file = open("query.txt", "w+")
        file.write(text)
        file.close()

    def replace(
        old,
        new,
        search_from_match: str = None,
        search_from_match_occurrence: int = None,
        count: int = 1,
    ):
        # Read in the file
        with open("query.txt", "r") as file:
            filedata = file.read()

        def find_nth(haystack, needle, n):
            start = haystack.lower().find(needle)
            while start >= 0 and n > 1:
                start = haystack.lower().find(needle, start + len(needle))
                n -= 1
            return start

        if search_from_match and search_from_match_occurrence:
            position = find_nth(
                filedata, search_from_match, search_from_match_occurrence
            )
            filedata_pre = filedata[:position]
            filedata_post = filedata[position:].replace(old, new, count)
            filedata = filedata_pre + filedata_post
        else:
            filedata = filedata.replace(old, new, count)

        # Write the file out again
        with open("query.txt", "w") as file:
            file.write(filedata)

    aggr_vars = collections.defaultdict(list)  # type: dict

    def convert_node_arg(node_arg):
        if isinstance(node_arg, Identifier):
            if node_arg in aggr_vars.keys():
                grp_var = aggr_vars[node_arg].pop(0).n3()
                return grp_var
            else:
                return node_arg.n3()
        elif isinstance(node_arg, CompValue):
            return "{" + node_arg.name + "}"
        elif isinstance(node_arg, Expr):
            return "{" + node_arg.name + "}"
        elif isinstance(node_arg, str):
            return node_arg
        else:
            raise ExpressionNotCoveredException(
                "The expression {0} might not be covered yet.".format(node_arg)
            )

    def sparql_query_text(node):
        """
         https://www.w3.org/TR/sparql11-query/#sparqlSyntax

        :param node:
        :return:
        """

        if isinstance(node, CompValue):
            # 18.2 Query Forms
            if node.name == "SelectQuery":
                overwrite("-*-SELECT-*- " + "{" + node.p.name + "}")

            # 18.2 Graph Patterns
            elif node.name == "BGP":
                # Identifiers or Paths
                # Negated path throws a type error. Probably n3() method of negated paths should be fixed
                triples = "".join(
                    triple[0].n3() + " " + triple[1].n3() + " " + triple[2].n3() + "."
                    for triple in node.triples
                )
                replace("{BGP}", triples)
                # The dummy -*-SELECT-*- is placed during a SelectQuery or Multiset pattern in order to be able
                # to match extended variables in a specific Select-clause (see "Extend" below)
                replace("-*-SELECT-*-", "SELECT", count=-1)
                # If there is no "Group By" clause the placeholder will simply be deleted. Otherwise there will be
                # no matching {GroupBy} placeholder because it has already been replaced by "group by variables"
                replace("{GroupBy}", "", count=-1)
                replace("{Having}", "", count=-1)
            elif node.name == "Join":
                replace("{Join}", "{" + node.p1.name + "}{" + node.p2.name + "}")  #
            elif node.name == "LeftJoin":
                replace(
                    "{LeftJoin}",
                    "{" + node.p1.name + "}OPTIONAL{{" + node.p2.name + "}}",
                )
            elif node.name == "Filter":
                if isinstance(node.expr, CompValue):
                    expr = node.expr.name
                else:
                    raise ExpressionNotCoveredException(
                        "This expression might not be covered yet."
                    )
                if node.p:
                    # Filter with p=AggregateJoin = Having
                    if node.p.name == "AggregateJoin":
                        replace("{Filter}", "{" + node.p.name + "}")
                        replace("{Having}", "HAVING({" + expr + "})")
                    else:
                        replace(
                            "{Filter}", "FILTER({" + expr + "}) {" + node.p.name + "}"
                        )
                else:
                    replace("{Filter}", "FILTER({" + expr + "})")

            elif node.name == "Union":
                replace(
                    "{Union}", "{{" + node.p1.name + "}}UNION{{" + node.p2.name + "}}"
                )
            elif node.name == "Graph":
                expr = "GRAPH " + node.term.n3() + " {{" + node.p.name + "}}"
                replace("{Graph}", expr)
            elif node.name == "Extend":
                query_string = open("query.txt", "r").read().lower()
                select_occurrences = query_string.count("-*-select-*-")
                replace(
                    node.var.n3(),
                    "(" + convert_node_arg(node.expr) + " as " + node.var.n3() + ")",
                    search_from_match="-*-select-*-",
                    search_from_match_occurrence=select_occurrences,
                )
                replace("{Extend}", "{" + node.p.name + "}")
            elif node.name == "Minus":
                expr = "{" + node.p1.name + "}MINUS{{" + node.p2.name + "}}"
                replace("{Minus}", expr)
            elif node.name == "Group":
                group_by_vars = []
                if node.expr:
                    for var in node.expr:
                        if isinstance(var, Identifier):
                            group_by_vars.append(var.n3())
                        else:
                            raise ExpressionNotCoveredException(
                                "This expression might not be covered yet."
                            )
                    replace("{Group}", "{" + node.p.name + "}")
                    replace("{GroupBy}", "GROUP BY " + " ".join(group_by_vars) + " ")
                else:
                    replace("{Group}", "{" + node.p.name + "}")
            elif node.name == "AggregateJoin":
                replace("{AggregateJoin}", "{" + node.p.name + "}")
                for agg_func in node.A:
                    if isinstance(agg_func.res, Identifier):
                        identifier = agg_func.res.n3()
                    else:
                        raise ExpressionNotCoveredException(
                            "This expression might not be covered yet."
                        )
                    aggr_vars[agg_func.res].append(agg_func.vars)

                    agg_func_name = agg_func.name.split("_")[1]
                    distinct = ""
                    if agg_func.distinct:
                        distinct = agg_func.distinct + " "
                    if agg_func_name == "GroupConcat":
                        replace(
                            identifier,
                            "GROUP_CONCAT"
                            + "("
                            + distinct
                            + agg_func.vars.n3()
                            + ";SEPARATOR="
                            + agg_func.separator.n3()
                            + ")",
                        )
                    else:
                        replace(
                            identifier,
                            agg_func_name.upper()
                            + "("
                            + distinct
                            + convert_node_arg(agg_func.vars)
                            + ")",
                        )
                    # For non-aggregated variables the aggregation function "sample" is automatically assigned.
                    # However, we do not want to have "sample" wrapped around non-aggregated variables. That is
                    # why we replace it. If "sample" is used on purpose it will not be replaced as the alias
                    # must be different from the variable in this case.
                    replace(
                        "(SAMPLE({0}) as {0})".format(convert_node_arg(agg_func.vars)),
                        convert_node_arg(agg_func.vars),
                    )
            elif node.name == "GroupGraphPatternSub":
                replace(
                    "GroupGraphPatternSub",
                    " ".join([convert_node_arg(pattern) for pattern in node.part]),
                )
            elif node.name == "TriplesBlock":
                print("triplesblock")
                replace(
                    "{TriplesBlock}",
                    "".join(
                        triple[0].n3()
                        + " "
                        + triple[1].n3()
                        + " "
                        + triple[2].n3()
                        + "."
                        for triple in node.triples
                    ),
                )

            # 18.2 Solution modifiers
            elif node.name == "ToList":
                raise ExpressionNotCoveredException(
                    "This expression might not be covered yet."
                )
            elif node.name == "OrderBy":
                order_conditions = []
                for c in node.expr:
                    if isinstance(c.expr, Identifier):
                        var = c.expr.n3()
                        if c.order is not None:
                            cond = c.order + "(" + var + ")"
                        else:
                            cond = var
                        order_conditions.append(cond)
                    else:
                        raise ExpressionNotCoveredException(
                            "This expression might not be covered yet."
                        )
                replace("{OrderBy}", "{" + node.p.name + "}")
                replace("{OrderConditions}", " ".join(order_conditions) + " ")
            elif node.name == "Project":
                project_variables = []
                for var in node.PV:
                    if isinstance(var, Identifier):
                        project_variables.append(var.n3())
                    else:
                        raise ExpressionNotCoveredException(
                            "This expression might not be covered yet."
                        )
                order_by_pattern = ""
                if node.p.name == "OrderBy":
                    order_by_pattern = "ORDER BY {OrderConditions}"
                replace(
                    "{Project}",
                    " ".join(project_variables)
                    + "{{"
                    + node.p.name
                    + "}}"
                    + "{GroupBy}"
                    + order_by_pattern
                    + "{Having}",
                )
            elif node.name == "Distinct":
                replace("{Distinct}", "DISTINCT {" + node.p.name + "}")
            elif node.name == "Reduced":
                replace("{Reduced}", "REDUCED {" + node.p.name + "}")
            elif node.name == "Slice":
                slice = "OFFSET " + str(node.start) + " LIMIT " + str(node.length)
                replace("{Slice}", "{" + node.p.name + "}" + slice)
            elif node.name == "ToMultiSet":
                if node.p.name == "values":
                    replace("{ToMultiSet}", "{{" + node.p.name + "}}")
                else:
                    replace(
                        "{ToMultiSet}", "{-*-SELECT-*- " + "{" + node.p.name + "}" + "}"
                    )

            # 18.2 Property Path

            # 17 Expressions and Testing Values
            # # 17.3 Operator Mapping
            elif node.name == "RelationalExpression":
                expr = convert_node_arg(node.expr)
                op = node.op
                if isinstance(list, type(node.other)):
                    other = (
                        "("
                        + ", ".join(convert_node_arg(expr) for expr in node.other)
                        + ")"
                    )
                else:
                    other = convert_node_arg(node.other)
                condition = "{left} {operator} {right}".format(
                    left=expr, operator=op, right=other
                )
                replace("{RelationalExpression}", condition)
            elif node.name == "ConditionalAndExpression":
                inner_nodes = " && ".join(
                    [convert_node_arg(expr) for expr in node.other]
                )
                replace(
                    "{ConditionalAndExpression}",
                    convert_node_arg(node.expr) + " && " + inner_nodes,
                )
            elif node.name == "ConditionalOrExpression":
                inner_nodes = " || ".join(
                    [convert_node_arg(expr) for expr in node.other]
                )
                replace(
                    "{ConditionalOrExpression}",
                    "(" + convert_node_arg(node.expr) + " || " + inner_nodes + ")",
                )
            elif node.name == "MultiplicativeExpression":
                left_side = convert_node_arg(node.expr)
                multiplication = left_side
                for i, operator in enumerate(node.op):  # noqa: F402
                    multiplication += (
                        operator + " " + convert_node_arg(node.other[i]) + " "
                    )
                replace("{MultiplicativeExpression}", multiplication)
            elif node.name == "AdditiveExpression":
                left_side = convert_node_arg(node.expr)
                addition = left_side
                for i, operator in enumerate(node.op):
                    addition += operator + " " + convert_node_arg(node.other[i]) + " "
                replace("{AdditiveExpression}", addition)
            elif node.name == "UnaryNot":
                replace("{UnaryNot}", "!" + convert_node_arg(node.expr))

            # # 17.4 Function Definitions
            # # # 17.4.1 Functional Forms
            elif node.name.endswith("BOUND"):
                bound_var = convert_node_arg(node.arg)
                replace("{Builtin_BOUND}", "bound(" + bound_var + ")")
            elif node.name.endswith("IF"):
                arg2 = convert_node_arg(node.arg2)
                arg3 = convert_node_arg(node.arg3)

                if_expression = (
                    "IF(" + "{" + node.arg1.name + "}, " + arg2 + ", " + arg3 + ")"
                )
                replace("{Builtin_IF}", if_expression)
            elif node.name.endswith("COALESCE"):
                replace(
                    "{Builtin_COALESCE}",
                    "COALESCE("
                    + ", ".join(convert_node_arg(arg) for arg in node.arg)
                    + ")",
                )
            elif node.name.endswith("Builtin_EXISTS"):
                # The node's name which we get with node.graph.name returns "Join" instead of GroupGraphPatternSub
                # According to https://www.w3.org/TR/2013/REC-sparql11-query-20130321/#rExistsFunc
                # ExistsFunc can only have a GroupGraphPattern as parameter. However, when we print the query algebra
                # we get a GroupGraphPatternSub
                replace("{Builtin_EXISTS}", "EXISTS " + "{{" + node.graph.name + "}}")
                traverse(node.graph, visitPre=sparql_query_text)
                return node.graph
            elif node.name.endswith("Builtin_NOTEXISTS"):
                # The node's name which we get with node.graph.name returns "Join" instead of GroupGraphPatternSub
                # According to https://www.w3.org/TR/2013/REC-sparql11-query-20130321/#rNotExistsFunc
                # NotExistsFunc can only have a GroupGraphPattern as parameter. However, when we print the query algebra
                # we get a GroupGraphPatternSub
                print(node.graph.name)
                replace(
                    "{Builtin_NOTEXISTS}", "NOT EXISTS " + "{{" + node.graph.name + "}}"
                )
                traverse(node.graph, visitPre=sparql_query_text)
                return node.graph
            # # # # 17.4.1.5 logical-or: Covered in "RelationalExpression"
            # # # # 17.4.1.6 logical-and: Covered in "RelationalExpression"
            # # # # 17.4.1.7 RDFterm-equal: Covered in "RelationalExpression"
            elif node.name.endswith("sameTerm"):
                replace(
                    "{Builtin_sameTerm}",
                    "SAMETERM("
                    + convert_node_arg(node.arg1)
                    + ", "
                    + convert_node_arg(node.arg2)
                    + ")",
                )
            # # # # IN: Covered in "RelationalExpression"
            # # # # NOT IN: Covered in "RelationalExpression"

            # # # 17.4.2 Functions on RDF Terms
            elif node.name.endswith("Builtin_isIRI"):
                replace("{Builtin_isIRI}", "isIRI(" + convert_node_arg(node.arg) + ")")
            elif node.name.endswith("Builtin_isBLANK"):
                replace(
                    "{Builtin_isBLANK}", "isBLANK(" + convert_node_arg(node.arg) + ")"
                )
            elif node.name.endswith("Builtin_isLITERAL"):
                replace(
                    "{Builtin_isLITERAL}",
                    "isLITERAL(" + convert_node_arg(node.arg) + ")",
                )
            elif node.name.endswith("Builtin_isNUMERIC"):
                replace(
                    "{Builtin_isNUMERIC}",
                    "isNUMERIC(" + convert_node_arg(node.arg) + ")",
                )
            elif node.name.endswith("Builtin_STR"):
                replace("{Builtin_STR}", "STR(" + convert_node_arg(node.arg) + ")")
            elif node.name.endswith("Builtin_LANG"):
                replace("{Builtin_LANG}", "LANG(" + convert_node_arg(node.arg) + ")")
            elif node.name.endswith("Builtin_DATATYPE"):
                replace(
                    "{Builtin_DATATYPE}", "DATATYPE(" + convert_node_arg(node.arg) + ")"
                )
            elif node.name.endswith("Builtin_IRI"):
                replace("{Builtin_IRI}", "IRI(" + convert_node_arg(node.arg) + ")")
            elif node.name.endswith("Builtin_BNODE"):
                replace("{Builtin_BNODE}", "BNODE(" + convert_node_arg(node.arg) + ")")
            elif node.name.endswith("STRDT"):
                replace(
                    "{Builtin_STRDT}",
                    "STRDT("
                    + convert_node_arg(node.arg1)
                    + ", "
                    + convert_node_arg(node.arg2)
                    + ")",
                )
            elif node.name.endswith("Builtin_STRLANG"):
                replace(
                    "{Builtin_STRLANG}",
                    "STRLANG("
                    + convert_node_arg(node.arg1)
                    + ", "
                    + convert_node_arg(node.arg2)
                    + ")",
                )
            elif node.name.endswith("Builtin_UUID"):
                replace("{Builtin_UUID}", "UUID()")
            elif node.name.endswith("Builtin_STRUUID"):
                replace("{Builtin_STRUUID}", "STRUUID()")

            # # # 17.4.3 Functions on Strings
            elif node.name.endswith("Builtin_STRLEN"):
                replace(
                    "{Builtin_STRLEN}", "STRLEN(" + convert_node_arg(node.arg) + ")"
                )
            elif node.name.endswith("Builtin_SUBSTR"):
                args = [convert_node_arg(node.arg), node.start]
                if node.length:
                    args.append(node.length)
                expr = "SUBSTR(" + ", ".join(args) + ")"
                replace("{Builtin_SUBSTR}", expr)
            elif node.name.endswith("Builtin_UCASE"):
                replace("{Builtin_UCASE}", "UCASE(" + convert_node_arg(node.arg) + ")")
            elif node.name.endswith("Builtin_LCASE"):
                replace("{Builtin_LCASE}", "LCASE(" + convert_node_arg(node.arg) + ")")
            elif node.name.endswith("Builtin_STRSTARTS"):
                replace(
                    "{Builtin_STRSTARTS}",
                    "STRSTARTS("
                    + convert_node_arg(node.arg1)
                    + ", "
                    + convert_node_arg(node.arg2)
                    + ")",
                )
            elif node.name.endswith("Builtin_STRENDS"):
                replace(
                    "{Builtin_STRENDS}",
                    "STRENDS("
                    + convert_node_arg(node.arg1)
                    + ", "
                    + convert_node_arg(node.arg2)
                    + ")",
                )
            elif node.name.endswith("Builtin_CONTAINS"):
                replace(
                    "{Builtin_CONTAINS}",
                    "CONTAINS("
                    + convert_node_arg(node.arg1)
                    + ", "
                    + convert_node_arg(node.arg2)
                    + ")",
                )
            elif node.name.endswith("Builtin_STRBEFORE"):
                replace(
                    "{Builtin_STRBEFORE}",
                    "STRBEFORE("
                    + convert_node_arg(node.arg1)
                    + ", "
                    + convert_node_arg(node.arg2)
                    + ")",
                )
            elif node.name.endswith("Builtin_STRAFTER"):
                replace(
                    "{Builtin_STRAFTER}",
                    "STRAFTER("
                    + convert_node_arg(node.arg1)
                    + ", "
                    + convert_node_arg(node.arg2)
                    + ")",
                )
            elif node.name.endswith("Builtin_ENCODE_FOR_URI"):
                replace(
                    "{Builtin_ENCODE_FOR_URI}",
                    "ENCODE_FOR_URI(" + convert_node_arg(node.arg) + ")",
                )
            elif node.name.endswith("Builtin_CONCAT"):
                expr = "CONCAT({vars})".format(
                    vars=", ".join(convert_node_arg(elem) for elem in node.arg)
                )
                replace("{Builtin_CONCAT}", expr)
            elif node.name.endswith("Builtin_LANGMATCHES"):
                replace(
                    "{Builtin_LANGMATCHES}",
                    "LANGMATCHES("
                    + convert_node_arg(node.arg1)
                    + ", "
                    + convert_node_arg(node.arg2)
                    + ")",
                )
            elif node.name.endswith("REGEX"):
                args = [convert_node_arg(node.text), convert_node_arg(node.pattern)]
                expr = "REGEX(" + ", ".join(args) + ")"
                replace("{Builtin_REGEX}", expr)
            elif node.name.endswith("REPLACE"):
                replace(
                    "{Builtin_REPLACE}",
                    "REPLACE("
                    + convert_node_arg(node.arg)
                    + ", "
                    + convert_node_arg(node.pattern)
                    + ", "
                    + convert_node_arg(node.replacement)
                    + ")",
                )

            # # # 17.4.4 Functions on Numerics
            elif node.name == "Builtin_ABS":
                replace("{Builtin_ABS}", "ABS(" + convert_node_arg(node.arg) + ")")
            elif node.name == "Builtin_ROUND":
                replace("{Builtin_ROUND}", "ROUND(" + convert_node_arg(node.arg) + ")")
            elif node.name == "Builtin_CEIL":
                replace("{Builtin_CEIL}", "CEIL(" + convert_node_arg(node.arg) + ")")
            elif node.name == "Builtin_FLOOR":
                replace("{Builtin_FLOOR}", "FLOOR(" + convert_node_arg(node.arg) + ")")
            elif node.name == "Builtin_RAND":
                replace("{Builtin_RAND}", "RAND()")

            # # # 17.4.5 Functions on Dates and Times
            elif node.name == "Builtin_NOW":
                replace("{Builtin_NOW}", "NOW()")
            elif node.name == "Builtin_YEAR":
                replace("{Builtin_YEAR}", "YEAR(" + convert_node_arg(node.arg) + ")")
            elif node.name == "Builtin_MONTH":
                replace("{Builtin_MONTH}", "MONTH(" + convert_node_arg(node.arg) + ")")
            elif node.name == "Builtin_DAY":
                replace("{Builtin_DAY}", "DAY(" + convert_node_arg(node.arg) + ")")
            elif node.name == "Builtin_HOURS":
                replace("{Builtin_HOURS}", "HOURS(" + convert_node_arg(node.arg) + ")")
            elif node.name == "Builtin_MINUTES":
                replace(
                    "{Builtin_MINUTES}", "MINUTES(" + convert_node_arg(node.arg) + ")"
                )
            elif node.name == "Builtin_SECONDS":
                replace(
                    "{Builtin_SECONDS}", "SECONDS(" + convert_node_arg(node.arg) + ")"
                )
            elif node.name == "Builtin_TIMEZONE":
                replace(
                    "{Builtin_TIMEZONE}", "TIMEZONE(" + convert_node_arg(node.arg) + ")"
                )
            elif node.name == "Builtin_TZ":
                replace("{Builtin_TZ}", "TZ(" + convert_node_arg(node.arg) + ")")

            # # # 17.4.6 Hash functions
            elif node.name == "Builtin_MD5":
                replace("{Builtin_MD5}", "MD5(" + convert_node_arg(node.arg) + ")")
            elif node.name == "Builtin_SHA1":
                replace("{Builtin_SHA1}", "SHA1(" + convert_node_arg(node.arg) + ")")
            elif node.name == "Builtin_SHA256":
                replace(
                    "{Builtin_SHA256}", "SHA256(" + convert_node_arg(node.arg) + ")"
                )
            elif node.name == "Builtin_SHA384":
                replace(
                    "{Builtin_SHA384}", "SHA384(" + convert_node_arg(node.arg) + ")"
                )
            elif node.name == "Builtin_SHA512":
                replace(
                    "{Builtin_SHA512}", "SHA512(" + convert_node_arg(node.arg) + ")"
                )

            # Other
            elif node.name == "values":
                columns = []
                for key in node.res[0].keys():
                    if isinstance(key, Identifier):
                        columns.append(key.n3())
                    else:
                        raise ExpressionNotCoveredException(
                            "The expression {0} might not be covered yet.".format(key)
                        )
                values = "VALUES (" + " ".join(columns) + ")"

                rows = ""
                for elem in node.res:
                    row = []
                    for term in elem.values():
                        if isinstance(term, Identifier):
                            row.append(
                                term.n3()
                            )  # n3() is not part of Identifier class but every subclass has it
                        elif isinstance(term, str):
                            row.append(term)
                        else:
                            raise ExpressionNotCoveredException(
                                "The expression {0} might not be covered yet.".format(
                                    term
                                )
                            )
                    rows += "(" + " ".join(row) + ")"

                replace("values", values + "{" + rows + "}")
            elif node.name == "ServiceGraphPattern":
                replace(
                    "{ServiceGraphPattern}",
                    "SERVICE "
                    + convert_node_arg(node.term)
                    + "{"
                    + node.graph.name
                    + "}",
                )
                traverse(node.graph, visitPre=sparql_query_text)
                return node.graph
            # else:
            #     raise ExpressionNotCoveredException("The expression {0} might not be covered yet.".format(node.name))

    traverse(query_algebra.algebra, visitPre=sparql_query_text)
    query_from_algebra = open("query.txt", "r").read()
    os.remove("query.txt")

    return query_from_algebra


def pprintAlgebra(q):
    def pp(p, ind="    "):
        # if isinstance(p, list):
        #     print "[ "
        #     for x in p: pp(x,ind)
        #     print "%s ]"%ind
        #     return
        if not isinstance(p, CompValue):
            print(p)
            return
        print("%s(" % (p.name,))
        for k in p:
            print(
                "%s%s ="
                % (
                    ind,
                    k,
                ),
                end=" ",
            )
            pp(p[k], ind + "    ")
        print("%s)" % ind)

    try:
        pp(q.algebra)
    except AttributeError:
        # it's update, just a list
        for x in q:
            pp(x)
