# Copyright 2026 SigmaSRC, Inc. All Rights Reserved.

"""Translator from Fuel to Python.

The translator takes a parse tree of a Fuel script and produces
Python source code.
"""

# Python imports
import re

# Sigma imports
from sigma.util.fuelset import FuelSet

# Fuel compiler imports
from sigma.fuelc import modreg
from sigma.fuelc import symtab
from sigma.fuelc import astnode
from sigma.fuelc import typesys
from sigma.fuelc import literals

_RECOGNIZED_ESCAPE_CHARS = set("abfnrtv")

_ESCAPE_RE = re.compile(
    r"""\\(\'|\"|\\|[abfnrtv]|x[0-9a-fA-F]{1,2}|[0-7]{1,3})|(\\.)""",
    re.DOTALL
)

def _fix_string_repr(node_repr):
    """Ensure a string literal is valid Python 3 (no unrecognized escapes)."""
    if node_repr.startswith(('r"', "r'", 'R"', "R'")):
        return node_repr
    if node_repr[:3] in ('"""', "'''"):
        q = node_repr[:3]
    else:
        q = node_repr[0]
    content = node_repr[len(q):-len(q)]
    has_recognized = False
    has_unrecognized = False
    for m in _ESCAPE_RE.finditer(content):
        if m.group(2) is not None:
            has_unrecognized = True
        elif m.group(1) is not None:
            has_recognized = True
    if not has_unrecognized:
        return node_repr
    if not has_recognized:
        return 'r' + node_repr
    def _double_unrecognized(m):
        if m.group(2) is not None:
            return '\\' + m.group(2)
        return m.group(0)
    fixed = _ESCAPE_RE.sub(_double_unrecognized, content)
    return q + fixed + q

def xstr(x):
    s = str(x)
    s = re.sub(r"\(\n *", "(", s)
    return " ".join(s.split())

def indent(s):
    return "".join(["    %s\n" % line for line in s.splitlines()])

class Translator(symtab.SymbolTable):

    def __init__(self, next=None, errorhandler=None,
                 moduleregistry=None, packagename=None,
                 major=False):
        symtab.SymbolTable.__init__(self, next, errorhandler)
        self.major = major
        if moduleregistry is None:
            if isinstance(next, Translator):
                moduleregistry = next.moduleregistry
            if moduleregistry is None:
                moduleregistry = modreg.ModuleRegistry()
        self.moduleregistry = moduleregistry
        if packagename is None and isinstance(next, Translator):
            packagename = next.packagename
        self.packagename = packagename

    def define(self, name, node=None, type=None, value=None):
        self.checkoverride(name)
        return symtab.SymbolTable.define(self, name, node, type, value)

    def adddefn(self, name, defn):
        self.checkoverride(name)
        return symtab.SymbolTable.adddefn(self, name, defn)

    def checkoverride(self, name):
        """Check for name overriding errors.

        Check for name in surrounding scopes, up to next "major" (proc
        or func) scope.  Note that checking in this scope is already
        done by the SymbolTable class.

        """
        if self.major:
            return
        scope = self.next
        while isinstance(scope, Translator):
            if name in scope.names:
                self.error("overriding definition of %r", name)
                break
            if scope.major:
                break
            scope = scope.next

    # Translating whole programs

    def translate(self, node):
        """Return a string representing the textual translation of the node."""
        if node is None:
            return ""
        rv = self.visit("translate_", node)
        if rv is None:
            self.error("translate(%s) returned None", xstr(node))
            rv = ""
        return rv

    def translate_OuterStatements(self, node):
        if node.doc is not None:
            doc = literals.evalString(node.doc.str.repr)
            self.define("__doc__", node.doc, typesys.BasicStr, doc)
        texts = map(self.translate, node.stmts)
        return "".join(texts)

    def translate_Import(self, node):
        if node.fromname is not None:
            prefix = self.extract_prefix(node.fromname)
            if prefix.startswith("."):
                if self.packagename:
                    if prefix == ".":
                        prefix = self.packagename
                    else:
                        prefix = self.packagename + prefix
                else:
                    if prefix == ".":
                        prefix = None
                    else:
                        prefix = prefix[1:]
        else:
            prefix = None
        texts = []
        for subnode in node.importnames:
            impname = subnode.importname.name
            asname = subnode.asname.name
            if prefix:
                try:
                    defn = self.moduleregistry.importfrom(prefix, impname)
                except modreg.LoadError as err:
                    self.error("import failure:", str(err))
                    self.define(asname, subnode, typesys.BasicError)
                else:
                    self.define(asname, subnode, defn.type, defn.value)
                    if defn.type is typesys.BasicModule:
                        # It's "from <package> import <module>"
                        texts.append("from %s import %s_fuel as %s\n" %
                                     (prefix, impname, asname))
                    else:
                        # It's "from [<package>.]<module> import <object>"
                        texts.append("from %s_fuel import %s as %s\n" %
                                     (prefix, impname, asname))
            else:
                try:
                    defn = self.moduleregistry.importmodule(impname)
                except modreg.LoadError as err:
                    self.error("import failure:", str(err))
                    self.define(asname, subnode, typesys.BasicError)
                else:
                    self.define(asname, subnode, defn.type, defn.value)
                    texts.append("import %s_fuel as %s\n" % (impname, asname))
        return "".join(texts)

    def extract_prefix(self, node):
        if node.isrel:
            s = "."
        else:
            s = ""
        qname = node.qname
        if qname is not None:
            if isinstance(qname, astnode.Name):
                s += qname.name
            else:
                assert isinstance(qname, astnode.QualName)
                s += ".".join([n.name for n in qname.names])
        return s

    def translate_TypeDef(self, node):
        name = node.name.name
        type = self.evaltype(node.type)
        self.define(name, node, typesys.BasicType, type)
        return "# type %s = %s\n" % (name, str(type))

    def translate_ConstDef(self, node):
        name = node.name.name
        defn = self.define(name, node)
        text, value, type = self.eval(node.expr)
        if node.type is not None:
            declared_type = self.evaltype(node.type)
            if not typesys.accepts(declared_type, type):
                self.error(
                    "declared type (%s) doesn't accept actual type (%s)",
                    declared_type,
                    type)
                return ""
            type = declared_type
        defn.settype(type)
        if value is not None:
            defn.setvalue(value)
        if (value is None and
            type is not typesys.BasicVoid and
            type is not typesys.BasicError):
            self.error("constant value is not constant")
        return "%s = %s\n" % (name, text)

    def translate_InterfaceDef(self, node):
        classname = node.name.name
        defn = self.define(classname, node, typesys.BasicType)
        if node.doc is not None:
            doc = literals.evalString(node.doc.str.repr)
            defn.setdoc(doc)
        body = node.body
        if not body:
            attrdefs = []
        elif isinstance(body, astnode.InterfaceAttrDefs):
            attrdefs = body.defs
        else:
            assert isinstance(body, astnode.InterfaceAttrDef)
            attrdefs = [body]
        defs = []
        names = FuelSet()
        for d in attrdefs:
            aname = d.name.name
            if aname in names:
                self.error("duplicate class attribute name '%s'", aname)
                continue
            names.add(aname)
            atype = self.evaltype(d.type)
            if d.formals:
                s, argnames, argtypes, argdefaults = \
                   self.scan_formals(d.formals.formals)
                atype = typesys.Function(argnames,
                                         argtypes,
                                         self.extract_defaults(argdefaults),
                                         atype)
            adefn = symtab.SymbolDefinition(aname, d, atype)
            defs.append((aname, adefn))
        defn.setvalue(typesys.Interface(classname, tuple(defs)))
        return "# interface %s\n" % classname

    def extract_defaults(self, argdefaults):
        L = []
        oktypes = (int, float, str)
        for i, adef in enumerate(argdefaults):
            if adef is not None:
                aexpr, aval, atype = adef
                if aexpr is None or not isinstance(aval, oktypes):
                    aval = None
                L.append(aval)
            else:
                assert len(L) == 0, (L, i, adef)
        return tuple(L)

    def translate_StructDef(self, node):
        assert isinstance(node, astnode.StructDef)

        structname = node.name.name
        defn = self.define(structname, node, typesys.BasicType)
        if node.doc is not None:
            doc = literals.evalString(node.doc.str.repr)
            defn.setdoc(doc)

        classheadtext = "class %s(FuelStruct):\n" % node.name.name

        body = node.body
        if not body:
            attrdefs = []
        elif isinstance(body, astnode.StructAttrDefs):
            attrdefs = body.defs
        else:
            assert isinstance(body, astnode.StructAttrDef)
            attrdefs = [body]

        argdefs = [] # tuple of (name, defaulttext or None)
        defs = []
        names = FuelSet()
        for d in attrdefs:
            aname = d.name.name
            if aname in names:
                self.error("duplicate struct attribute name '%s'", aname)
                continue
            names.add(aname)
            atype = self.evaltype(d.type)
            adefn = symtab.SymbolDefinition(aname, d, atype)
            deftext = None
            defvalue = () # Marker for missing default
            if d.expr is not None:
                deftext, defvalue, deftype = self.eval(d.expr)
                if not typesys.accepts(atype, deftype):
                    self.error("default value for attribute '%s' does not "
                               "match declared type", aname)
            adefn.value = defvalue
            defs.append((aname, adefn))
            argdefs.append((aname, deftext))

        defn.setvalue(typesys.Struct(structname, tuple(defs)))

        argtexts = []
        bodytexts = []
        for name, defaulttext in argdefs:
            argtexts.append(", %s" % name)
            if defaulttext is not None:
                argtexts.append("=None")
                if defaulttext != "None":
                    bodytexts.append("if %s is None:\n    %s = %s\n" %
                                     (name, name, defaulttext))
            bodytexts.append("self.%s = %s\n" % (name, name))

        headtext = "def __init__(self%s):\n" % "".join(argtexts)
        inittext = headtext + indent("".join(bodytexts or ["pass\n"]))

        return classheadtext + indent(inittext)

    func_type = None

    def get_func_type(self):
        # A little hack so that a return statement can find out the
        # function return type which it must match
        if self.func_type is not None:
            return self.func_type
        if self.next is None:
            return none
        return self.next.get_func_type()

    def translate_ProcDef(self, node):
        name = node.name.name
        scope, argnames, argtypes, argdefaults = \
               self.scan_formals(node.formals.formals)
        scope.func_type = typesys.BasicVoid
        signature = typesys.Function(argnames,
                                     argtypes,
                                     self.extract_defaults(argdefaults),
                                     typesys.BasicVoid)
        bodytext = scope.process_defaults(argnames, argdefaults)
        bodytext += scope.translate(node.body) or "pass\n"
        bodytext = indent(bodytext)
        defn = self.define(name, node, signature)
        if node.doc is not None:
            doc = literals.evalString(node.doc.str.repr)
            defn.setdoc(doc)
        return "def %s(%s):\n%s" % (name,
                                    self.gen_formals(argnames, argdefaults),
                                    bodytext)

    def translate_FuncDef(self, node):
        name = node.name.name
        scope, argnames, argtypes, argdefaults = \
               self.scan_formals(node.formals.formals)
        type = self.evaltype(node.type)
        scope.func_type = type
        signature = typesys.Function(argnames,
                                     argtypes,
                                     self.extract_defaults(argdefaults),
                                     type)
        bodytext = scope.process_defaults(argnames, argdefaults)
        if not self.checkreturns(node.body):
            self.error("not all paths through this function reach a return")
        if node.body is not None:
            bodytext += scope.translate(node.body)
        bodytext = indent(bodytext)
        defn = self.define(name, node, signature)
        if node.doc is not None:
            doc = literals.evalString(node.doc.str.repr)
            defn.setdoc(doc)
        return "def %s(%s):\n%s" % (name,
                                    self.gen_formals(argnames, argdefaults),
                                    bodytext)

    def gen_formals(self, argnames, argdefaults):
        formals = []
        for aname, adef in zip(argnames, argdefaults):
            if adef is None:
                formals.append(aname)
            else:
                formals.append("%s=None" % aname)
        return ", ".join(formals)

    def scan_formals(self, formals):
        scope = Translator(self, major=True)
        argtypes = []
        argnames = []
        argdefaults = []
        lastdefault = None
        for f in formals:
            fname, ftype, fexpr = f.name.name, f.type, f.expr
            argnames.append(fname)
            fd = scope.define(fname, formals)
            ftype = self.evaltype(ftype)
            fd.settype(ftype)
            if fexpr is None:
                if lastdefault is not None:
                    self.error("arguments without defaults cannot follow "
                               "arguments with defaults")
                fdefault = None
            else:
                ftext, fvalue, fvaltype = fdefault = scope.eval(fexpr)
                if not typesys.accepts(ftype, fvaltype):
                    self.error("argument type (%s) doesn't accept "
                               "default value's type (%s)",
                               ftype,
                               fvaltype)
            argtypes.append(ftype)
            argdefaults.append(fdefault)
            lastdefault = fdefault
        return scope, tuple(argnames), tuple(argtypes), tuple(argdefaults)

    def process_defaults(self, argnames, argdefaults):
        lines = []
        for aname, adef in zip(argnames, argdefaults):
            if adef is None:
                continue
            ftext, fvalue, fvaltype = adef
            lines.append("if %s is None:\n" % aname)
            lines.append("    %s = %s\n" % (aname, ftext))
        return "".join(lines)

    def translate_InnerStatements(self, node):
        translations = []
        for stmt in node.stmts:
            translations.append(self.translate(stmt))
        return "".join(translations)

    def translate_LetDef(self, node):
        name = node.name.name
        defn = self.define(name, node)
        if node.type:
            type = self.evaltype(node.type)
        else:
            type = None
        text, value, etype = self.eval(node.expr)
        if type is None:
            type = etype
        else:
            if not typesys.accepts(type, etype):
                self.error(
                    "declared type (%s) doesn't accept actual type (%s)",
                    type,
                    etype)
        defn.settype(type)
        if value is not None:
            defn.setvalue(value)
        return "%s = %s\n" % (name, text)

    def translate_FunCall(self, node):
        text, value, type = self.compile_call(node.qname, node.args, "proc")
        return text and text + "\n" or ""

    def extract_args(self, args):
        assert isinstance(args, astnode.CallArgs)
        if not args.args:
            return []
        if isinstance(args.args, astnode.Expressions):
            return args.args.exprs
        else:
            return [args.args]

    def translate_IfBlock(self, node):
        texts = []
        keyword = "if"
        for expr, stmts in node.choices:
            if expr is None:
                texts.append("else:\n")
            else:
                etext, evalue, etype = self.eval(expr)
                if not typesys.accepts(typesys.BasicBool, etype):
                    self.error("if/elif requires bool, not %s", etype)
                texts.append("%s %s:\n" % (keyword, etext))
            scope = Translator(self)
            bodytext = scope.translate(stmts) or "pass\n"
            texts.append(indent(bodytext))
            keyword = "elif"
        return "".join(texts)

    def translate_ForBlock(self, node):
        name = node.name.name
        stext, svalue, stype = self.eval(node.expr)
        etype = typesys.BasicError
        if stype is not typesys.BasicError:
            if isinstance(stype, typesys.Set):
                etype = stype.etype
            else:
                self.error("for statement requires set expression, not %s",
                           stype)
        scope = Translator(self)
        scope.define(name, node, etype)
        bodytext = scope.translate(node.stmts) or "pass\n"
        return "for %s in %s:\n" % (name, stext) + indent(bodytext)

    def translate_ReturnStatement(self, node):
        ftype = self.get_func_type()
        if ftype is None:
            self.error("return statement outside function/procedure")
            return ""
        if ftype is typesys.BasicVoid:
            if node.expr is not None:
                self.error("return in procedure should not have an expression")
            return "return\n"
        # We're in a function
        if node.expr is None:
            self.error("return in function should have an expression")
            return "return None\n" # Whatever
        text, value, type = self.eval(node.expr)
        if type is typesys.BasicVoid:
            self.error("can't return nil from a function")
        elif not typesys.accepts(ftype, type):
            self.error("function type (%s) doesn't match "
                       "return expression type (%s)",
                       ftype, type)
        return "return %s\n" % text

    # Checking whether each path through a function ends in a return statement

    def checkreturns(self, node):
        if node is None:
            return False
        return self.visit("checkreturns_", node)

    def checkreturns_InnerStatements(self, node):
        return bool(node.stmts) and self.checkreturns(node.stmts[-1])

    def checkreturns_ReturnStatement(self, node):
        return True

    def checkreturns_Action(self, node):
        return False

    def checkreturns_LetDef(self, node):
        return False

    def checkreturns_ForBlock(self, node):
        return False # Because we could be looping over an empty set

    def checkreturns_IfBlock(self, node):
        else_seen = False
        for expr, stmts in node.choices:
            if not self.checkreturns(stmts):
                return False
            if expr is None:
                else_seen = True
        return else_seen

    # Translating, evaluating and typechecking expressions

    def eval(self, node):
        """Return a triple (text, value, type) for an expression.

        text is a string that is the translation of the expression.

        If the expression can be determined to have a constant value,
        then value is the constant, which may have different Python
        types depending on what we're translating.  If the expression
        cannot be determined to have a constant value, then value is
        None. 

        type is the type of the expression, generally something from
        typesys.

        Example #1: if the expression is abstract syntax for "x + y"
        when in the environment we know that x is 3 and y is 4, then
        text is "7", value is 7, and type is typesys.BasicInt.

        Example #2: Same expression, x is 3, y is an unknown integer.
        Then text is "3 + y", value is None, and type is again
        typesys.BasicInt.
        """
        rv = self.visit("eval_", node)
        if rv is None:
            self.error("eval(%s) returned None", xstr(node))
            rv = (None, None, typesys.BasicError)
        return rv

    def eval_Name(self, node):
        defn = self.lookup(node.name)
        if defn is None:
            self.error("name lookup for '%s' failed", node.name)
            return None, None, typesys.BasicError
        if defn.value is None and defn.type is not typesys.BasicVoid:
            text = defn.name
        elif defn.type is typesys.BasicModule:
            text = defn.name
        else:
            text = repr(defn.value)
        return text, defn.value, defn.type

    def eval_Number(self, node):
        numrepr = node.repr
        if len(numrepr) > 1 and numrepr[0] == '0' and numrepr[1:].isdigit():
            numrepr = '0o' + numrepr[1:]
        value = eval(numrepr) # Safety depends on tokenizer
        if isinstance(value, int):
            return numrepr, value, typesys.BasicInt
        if type(value) is float:
            return numrepr, value, typesys.BasicFloat
        self.error("only int and float constants are allowed")
        return None, None, typesys.BasicError

    def eval_String(self, node):
        value = literals.evalString(node.repr)
        if type(value) == str:
            return _fix_string_repr(node.repr), value, typesys.BasicStr
        self.error("unsupported string literal")
        return None, None, typesys.BasicError

    def eval_Expression(self, node):
        xtest, vtest, ttest = self.eval(node.test)
        if ttest != typesys.BasicBool:
            if ttest is not typesys.BasicError:
                self.error("test in conditional expression is not bool but %s",
                           ttest)
            return None, None, typesys.BasicError
        xleft, vleft, tleft = self.eval(node.left)
        xright, vright, tright = self.eval(node.right)
        type = typesys.coerce(tleft, tright)
        if type is None:
            self.error("branches of conditional expression"
                       " have incompatible types: %s : %s", tleft, tright)
        value = None
        text = "(%s if %s else %s)" % (xleft, xtest, xright)
        if vtest is not None:
            if vtest:
                if vleft is not None:
                    value = vleft
                    text = tleft
            else:
                if vright is not None:
                    value = vright
                    text = tright
        return text, value, type

    def eval_BinaryExpression(self, node):
        xleft, vleft, tleft = self.eval(node.left)
        xright, vright, tright = self.eval(node.right)
        if tleft is typesys.BasicError or tright is typesys.BasicError:
            return None, None, typesys.BasicError
        op = node.op.repr

        if (op in ("+", "-", "*", "/", "**") and 
            isinstance(tleft, typesys.Numeric) and
            isinstance(tright, typesys.Numeric)):
            if op in ("/", "**"):
                type = typesys.BasicFloat
                if vleft is not None:
                    vleft = float(vleft)
                if vright is not None:
                    vright = float(vright)
            else:
                type = typesys.coerce(tleft, tright)
            if vleft is None or vright is None:
                value = None
                text = "(%s %s %s)" % (xleft, op, xright)
            else:
                value = eval("vleft %s vright" % op)
                text = str(value)
            return text, value, type

        if (op in ("|", "&", "^", "-") and
            isinstance(tleft, typesys.Set) and
            isinstance(tright, typesys.Set)):
            if typesys.accepts(tleft, tright):
                type = tleft
            elif typesys.accepts(tright, tleft):
                type = tright
            else:
                self.error("incompatible set types for operator '%s'", op)
                return None, None, typesys.BasicError
            if vleft is None or vright is None:
                value = None
                text = "(%s %s %s)" % (xleft, op, xright)
            else:
                value = eval("vleft %s vright" % op)
                text = str(value)
            return text, value, type

        if op in ("==", "!="):
            if op == "==":
                isop = "is"
            else:
                isop = "is not"
            if tright is typesys.BasicVoid:
                return "(%s %s None)" % (xleft, isop), None, typesys.BasicBool
            if tleft is typesys.BasicVoid:
                return "(None %s %s)" % (isop, xright), None, typesys.BasicBool

        if op in ("<", "<=", "==", "!=", ">", ">="):
            if (isinstance(tleft, typesys.Numeric) and
                isinstance(tright, typesys.Numeric)):
                if vleft is None or vright is None:
                    value = None
                    text = "(%s %s %s)" % (xleft, op, xright)
                else:
                    value = eval("vleft %s vright" % op)
                    text = str(value)
                return text, value, typesys.BasicBool
            if tleft is typesys.BasicStr and tright is typesys.BasicStr:
                if vleft is None or vright is None:
                    value = None
                    text = "(%s %s %s)" % (xleft, op, xright)
                else:
                    value = eval("vleft %s vright" % op)
                    text = str(value)
                return text, value, typesys.BasicBool
            if (isinstance(tleft, typesys.Set) and
                isinstance(tright, typesys.Set)):
                if (typesys.accepts(tleft, tright) or
                    typesys.accepts(tright, tleft)):
                    if vleft is None or vright is None:
                        value = None
                        text = "(%s %s %s)" % (xleft, op, xright)
                    else:
                        value = eval("vleft %s vright" % op)
                        text = str(value)
                    return text, value, typesys.BasicBool
                self.error("incompatible set types for operator '%s'", op)
                return None, None, typesys.BasicError
            self.error("incompatible types for operator '%s'", op)

        if op in ("in", "not in"):
            if not isinstance(tright, typesys.Set):
                self.error("'[not] in' operator requires set on the right")
                return None, None, typesys.BasicError
            if tright.etype is typesys.BasicVoid:
                if op == "in":
                    return "False", False, typesys.BasicBool
                else:
                    assert op == "not in"
                    return "True", True, typesys.BasicBool
            if not typesys.accepts(tright.etype, tleft):
                self.error("'[not] in' operator: incompatible left operand")
                return None, None, typesys.BasicError
            if vleft is None or vright is None:
                value = None
                text = "(%s %s %s)" % (xleft, op, xright)
            else:
                value = eval("vleft %s vright" % op)
                text = str(value)
            return text, value, typesys.BasicBool

        if op in ("and", "or"):
            if tleft is typesys.BasicBool and tright is typesys.BasicBool:
                if vleft is None or vright is None:
                    value = None
                    text = "(%s %s %s)" % (xleft, op, xright)
                else:
                    value = eval("vleft %s vright" % op)
                    text = str(value)
                return text, value, typesys.BasicBool

        self.error("operator '%s' is not supported for types (%s, %s)",
                   op, tleft, tright)
        return None, None, typesys.BasicError

    def eval_UnaryExpression(self, node):
        text, value, type = self.eval(node.arg)
        if type is typesys.BasicError:
            return None, None, type

        if node.op == "not":
            if not typesys.accepts(typesys.BasicBool, type):
                self.error("'not' requires bool arg, not %s", type)
                return None, None, typesys.BasicBool
            text = "(not %s)" % text
            if value is not None:
                value = not value
                text = str(value)
            return text, value, type

        if node.op == "-":
            if not isinstance(type, typesys.Numeric):
                self.error("unary '-' requires numeric arg, not %s", type)
                return None, None, typesys.BasicError
            text = "(-%s)" % text
            if value is not None:
                value = -value
                text = str(value)
            return text, value, type

        assert False, "shouldn't get here"

    def eval_Set(self, node):
        body = node.body
        if body is None:
            # Empty set
            return "FuelSet()", FuelSet(), typesys.Set(typesys.BasicVoid)
        else:
            return self.eval(body)

    def eval_SetBody(self, node):
        if node.for_clause is not None:
            return self.set_comprehension(node)
        assert node.if_clause is None
        text1, value1, type1 = self.eval(node.expr)
        if type1 is typesys.BasicError:
            return None, None, type1
        if node.exprs is None:
            # A set with exactly one explicit item
            text = "FuelSet([%s])" % text1
            if value1 is None:
                value = None
            else:
                value = FuelSet([value1])
            if type1 is typesys.BasicError:
                type = type1
            else:
                type = typesys.Set(type1)
            return text, value, type
        # A set with more than one explicit item
        texts = [text1]
        if value1 is None:
            values = None
        else:
            values = [value1]
        type = type1
        for expr in node.exprs:
            texti, valuei, typei = self.eval(expr)
            if typei is typesys.BasicError:
                return None, None, typesys.BasicError
            texts.append(texti)
            if values is not None:
                if valuei is None:
                    values = None
                else:
                    values.append(valuei)
            type = typesys.coerce(type, typei)
        text = "FuelSet([%s])" % ", ".join(texts)
        if values is None:
            value = None
        else:
            value = FuelSet(values)
        return text, value, typesys.Set(type)

    def set_comprehension(self, node):
        assert node.exprs is None
        assert node.expr is not None
        for_clause = node.for_clause
        assert for_clause is not None
        if_clause = node.if_clause
        fname, fexpr = for_clause.name.name, for_clause.expr
        fetext, fevalue, fetype = self.eval(fexpr)
        if fetype is typesys.BasicError:
            etype = typesys.BasicError
        elif isinstance(fetype, typesys.Set):
            etype = fetype.etype
        else:
            self.error("for clause requires set expression, not %s", fetype)
            etype = typesys.BasicError
        scope = Translator(self)
        scope.define(fname, for_clause, etype)
        etext, evalue, etype = scope.eval(node.expr)
        if if_clause is not None:
            iftext, ifvalue, iftype = scope.eval(if_clause)
            if not typesys.accepts(typesys.BasicBool, iftype):
                self.error("if clause require bool as condition, not %s",
                           iftype)
        else:
            iftext = ifvalue = iftype = None
        if etype is typesys.BasicError:
            type = typesys.BasicError
        else:
            type = typesys.Set(etype)
        if iftext:
            iftext = " if %s" % iftext
        else:
            iftext = ""
        text = "FuelSet([%s for %s in %s%s])" % (etext, fname, fetext, iftext)
        return text, None, type

    def eval_IfClause(self, node):
        return self.eval(node.expr)

    def eval_StructConstructor(self, node):
        assert isinstance(node, astnode.StructConstructor)
        structdef = self.evaltype(node.qname)
        if isinstance(node.qname, astnode.Name):
            qname = node.qname.name
        else:
            qname = ".".join([n.name for n in node.qname.names])
        if not isinstance(structdef, typesys.Struct):
            self.error("'new %s': %s is not a struct type", qname, qname)
            return None, None, typesys.BasicError
        argtexts = []
        argset = FuelSet()
        if node.args:
            for kvp in node.args.kvps:
                aname = kvp.name.name
                if aname in argset:
                    self.error("duplicate attribute %s", aname)
                    continue
                argset.add(aname)
                adefn = structdef.lookup(aname)
                if adefn is None:
                    self.error("struct %s has no attribute %s", qname, aname)
                    continue
                argtext, argvalue, argtype = self.eval(kvp.expr)
                if not typesys.accepts(adefn.type, argtype):
                    self.error("incompatible type for struct %s attribute %s",
                               qname, aname)
                argtexts.append("%s=%s" % (aname, argtext))
        for aname, adefn in structdef.defs.items():
            if adefn.value == () and aname not in argset:
                self.error("missing attribute %s", aname)
        return qname + "(%s)" % ", ".join(argtexts), None, structdef

    def eval_FunCall(self, node):
        return self.compile_call(node.qname, node.args, "func")

    def eval_FieldRef(self, node):
        assert isinstance(node, astnode.FieldRef)
        (text, defn, type) = self.eval(node.obj)
        if type is typesys.BasicError:
            return None, None, type
        if type is typesys.BasicModule:
            assert isinstance(defn, modreg.Module)
            defn = defn.lookup(node.field)
            if defn is None:
                self.error("%s not found in %s", node.field, text)
                return None, None, typesys.BasicError
        else:
            if not isinstance(type, typesys.Interface):
                self.error("%s is not a class/struct instance nor a module",
                           text)
                return None, None, typesys.BasicError
            defn = type.lookup(node.field)
            if defn is None:
                self.error("class %s has no attribute %s", type.name,
                           node.field)
                return None, None, typesys.BasicError
        # XXX Should check that type is a data type
        return text + "." + node.field, None, defn.type

    def compile_call(self, qname, args, kind):
        # (This is separated in two just so that we don't have to
        # repeat the full error return triple many times)
        rv = self._compile_call(qname, args, kind)
        if rv is None:
            rv = None, None, typesys.BasicError
        return rv

    def _compile_call(self, qname, args, kind):
        assert kind in ("proc", "func")
        qtext, qvalue, qtype = self.eval(qname)
        if not isinstance(qtype, typesys.Function):
            if qtype is not typesys.BasicError:
                self.error("%s expected, %s found", kind, str(qtype))
            return None
        resulttype = qtype.resulttype
        if kind == "proc":
            if not typesys.accepts(typesys.BasicVoid, resulttype):
                self.error("proc expected, func found")
                return None
        else:
            if resulttype == typesys.BasicVoid:
                self.error("func expected, proc found")
                return None
        argtypes = qtype.argtypes
        ndefaults = qtype.ndefaults
        minargs = len(argtypes) - ndefaults
        maxargs = len(argtypes)
        args = self.extract_args(args)
        argtexts = []
        nargs = len(args)
        if not minargs <= nargs <= maxargs:
            if minargs == maxargs:
                self.error("%d argument(s) found, but %d expected",
                           nargs, minargs)
            else:
                self.error("%d argument(s) found, but %d upto %d expected",
                           nargs, minargs, maxargs)
            return None
        else:
            for i, (argtype, arg) in enumerate(zip(argtypes, args)):
                atext, avalue, atype = self.eval(arg)
                if not typesys.accepts(argtype, atype):
                    self.error("arg %d: type %s expected, not %s",
                               i+1, str(argtype), str(atype))
                if atext is not None:
                    argtexts.append(atext)
        # Special-case host.require()
        if "__require__" in qtype.argnames:
            argtexts.extend(self.add_require_args(qtype, args))
        return "%s(%s)" % (qtext, ", ".join(argtexts)), None, resulttype

    def add_require_args(self, qtype, args):
        iarg = list(qtype.argnames).index("__require__")
        argtype = qtype.argtypes[iarg]
        assert argtype is typesys.BasicBool
        arg = args[iarg]
        names = self.extractnames(arg)
        L = []
        for item in sorted(names.items(),
                           key=lambda item: ('.' in item[0], item[0])):
            L.append("%r: %s" % item)
        s = xstr(arg)
        return [repr(s), "{" + ", ".join(L) + "}"]

    # Extracting names

    def extractnames(self, node):
        # Return a dict mapping variable names to strings;
        # the strings represent expressions that calculate the variables
        d = self.visit("extractnames_", node)
##        if d is None:
##            d = {}
        return d

    def extractnames_FunCall(self, node):
        d = self.extractnames(node.qname)
        for arg in self.extract_args(node.args):
            da = self.extractnames(arg)
            if da:
                d.update(da)
        return d

    def extractnames_FieldRef(self, node):
        d = self.extractnames(node.obj);
        if node.is_all_fieldrefs():
            d = self.extractnames(node.obj);
            text, value, type = self.eval(node)
            d[str(node)] = text
        return d

    def extractnames_Name(self, node):
        text, value, type = self.eval(node)
        return {node.name: text}

    def extractnames_Expression(self, node):
        dtest = self.extractnames(node.test)
        dleft = self.extractnames(node.left)
        dright = self.extractnames(node.right)
        d = {}
        d.update(dtest)
        d.update(dleft)
        d.update(dright)
        return d

    def extractnames_BinaryExpression(self, node):
        dleft = self.extractnames(node.left)
        dright = self.extractnames(node.right)
        d = {}
        if dleft:
            d.update(dleft)
        if dright:
            d.update(dright)
        return d

    def extractnames_UnaryExpression(self, node):
        return self.extractnames(node.arg)

    def extractnames_Set(self, node):
        body = node.body
        if body is None:
            return {}
        else:
            return self.extractnames(body)

    def extractnames_SetBody(self, node):
        if node.for_clause is not None:
            d = self.extractnames(node.for_clause.expr)
            scope = Translator(self)
            scope.define(node.for_clause.name.name)
            v = scope.extractnames(node.for_clause.name)
            e = scope.extractnames(node.expr)
            if node.if_clause is not None:
                i = scope.extractnames(node.if_clause.expr)
                if i:
                    e.update(i)
            for key in v:
                if key in e:
                    del e[key]
            d.update(e)
        else:
            d = self.extractnames(node.expr)
            if node.exprs is not None:
                for e in node.exprs:
                    de = self.extractnames(e)
                    if de:
                        d.update(de)
        return d

    def extractnames_StructConstructor(self, node):
        if node.args is None:
            return {}
        else:
            return self.extractnames(node.args)

    def extractnames_KeyValuePairs(self, node):
        d = {}
        for kvp in node.kvps:
            dkvp = self.extractnames(kvp)
            if dkvp:
                d.update(dkvp)
        return d

    def extractnames_KeyValuePair(self, node):
        return self.extractnames(node.expr)

    def extractnames_Number(self, node):
        return {}

    def extractnames_String(self, node):
        return {}

    # Evaluating type expressions (e.g. 'set of T')

    def evaltype(self, node):
        """Return a type expression."""
        rv = self.visit("evaltype_", node)
        if rv is None:
            self.error("evaltype(%s) returned None", xstr(node))
            rv = typesys.BasicError
        return rv

    def evaltype_QualName(self, node):
        if len(node.names) > 2:
            self.error("can't have more than one dot in dotted type name")
            return typesys.BasicError
        assert len(node.names) == 2
        modname = node.names[0].name
        defn = self.lookup(modname)
        if defn is None or defn.type is not typesys.BasicModule:
            if defn.type is not typesys.BasicError:
                self.error("%s is not a module", modname)
            return typesys.BasicError
        assert isinstance(defn.value, modreg.Module)
        attrname = node.names[1].name
        adefn = defn.value.lookup(attrname)
        if adefn is None:
            self.error("%s.%s does not exist", modname, attrname)
            return typesys.BasicError
        if adefn.type is not typesys.BasicType:
            self.error("%s.%s is not a type", modname, attrname)
            return typesys.BasicType
        return adefn.value

    def evaltype_Name(self, node):
        defn = self.lookup(node.name)
        if defn is None:
            self.error("type name lookup for '%s' failed", node.name)
            return typesys.BasicError
        if defn.type is not typesys.BasicType:
            self.error("name lookup for '%s' returned a non-type", node.name)
            return typesys.BasicError
        if defn.value is None:
            self.error("name lookup for '%s' returned undefined", node.name)
            return typesys.BasicError
        return defn.value

    def evaltype_SetType(self, node):
        etype = self.evaltype(node.etype)
        if etype is typesys.BasicError:
            return etype
        else:
            return typesys.Set(etype)
