/**
  *  \file expr_annotator.cpp
  *  \brief Expressions
  *  \author Stefan Reuther
  *
  *  This file contains the class "Expr_annotator" which annotates an
  *  expression and turns it into the canonical form.
  */

INTERFACE:

#include "paranoid_visitor.h"
#include "expr_result.h"

class Source;
class Symbol_table;
class Function_symbol;
class Abstract_scope;
class Overload_resolver;

class Expr_annotator : public Paranoid_visitor<Expr_result> {
    Abstract_scope* current_scope;
 public:
    static const int PTR_DELEGATION_LIMIT = 100;
};

IMPLEMENTATION:

#include <cstring>
#include "scope.h"
#include "symbol_table.h"
#include "symbol_name.h"
#include "variable.h"
#include "function.h"
#include "overload_resolver.h"
#include "class.h"
#include "decl_read.h"
#include "typedef.h"
#include "implicit_conversion.h" // Conversion_op_map
#include "ptree_util.h"
#include "init_handler.h"

using namespace Opencxx;

/******************************* Utilities *******************************/

/** True if expression l has type t. */
static inline bool
has_type(Expr_result* l, const Type& t)
{
    return l->get_type().is_same_unqualified_type(t);
}

/** Give two similar types, merge their cv qualifiers. For example, given
    "int const **" and "int ** const", this returns "int const ** const".
    Throws if types are not similar. */
static Type
get_merged_cv_type(Type l, Type r)
{
    if (l.get_kind() == Type::k_Pointer && r.get_kind() == Type::k_Pointer) {
        Type sub = get_merged_cv_type(l.get_basis_type(), r.get_basis_type());
        return sub.make_pointer_type().with_qualifiers(l).with_qualifiers(r);
    } else if (l.get_kind() == Type::k_Member && r.get_kind() == Type::k_Member) {
        if (!l.get_class_type().is_same_unqualified_type(r.get_class_type()))
            compile_error("pointer types are not similar");
        Type sub = get_merged_cv_type(l.get_member_type(), r.get_member_type());
        return l.get_class_type().with_qualifiers(r.get_class_type()).make_member_type(sub);
    } else {
        if (!l.is_same_unqualified_type(r))
            compile_error("pointer types are not similar");
        return l.with_qualifiers(r);
    }
}

/** Get composite type for pointer comparison (5.9p2). */
static Type
get_composite_pointer_type(Expr_result* l, Expr_result* r)
{
    if (l->get_type().is_same_unqualified_type(r->get_type()))
        return l->get_type();

    /* if one argument is a null-pointer constant, convert it to the
       type of the other one */
    if (l->is_npc())
        return r->get_type();
    if (r->is_npc())
        return l->get_type();

    assert(l->get_type().get_kind() == Type::k_Pointer);
    assert(r->get_type().get_kind() == Type::k_Pointer);

    Type lbase = l->get_type().get_basis_type();
    Type rbase = r->get_type().get_basis_type();

    /* function types can't be compared this way */
    if (lbase.get_kind() == Type::k_Function || rbase.get_kind() == Type::k_Function)
        compile_error("comparing function pointer with incompatible pointer");

    /* if one is pointer-to-cv-void, convert other to cv-void */
    if (lbase.is_same_unqualified_type(rbase))
        return lbase.with_qualifiers(rbase).make_pointer_type();
    if (lbase.is_void())
        return lbase.with_qualifiers(rbase).make_pointer_type();
    if (rbase.is_void())
        return rbase.with_qualifiers(lbase).make_pointer_type();

    /* two object pointers. If one is class derived form the other,
       convert to that other. */
    if (lbase.is_class_type() && rbase.is_class_type()) {
        Class_symbol* lclass = downcast<Class_symbol*>(lbase.get_type_symbol());
        Class_symbol* rclass = downcast<Class_symbol*>(rbase.get_type_symbol());
        if (lclass->is_unique_base_class_of(rclass))
            return lbase.with_qualifiers(rbase).make_pointer_type();
        if (rclass->is_unique_base_class_of(lclass))
            return rbase.with_qualifiers(lbase).make_pointer_type();
        compile_error("comparing distinct pointer types `* " + lclass->get_name()
                      + "' and `* " + rclass->get_name() + "'");
    }

    return get_merged_cv_type(lbase, rbase).make_pointer_type();
}

/** Get composite type for pointer comparison (5.9p2). */
static Type
get_composite_mptr_type(Expr_result* l, Expr_result* r)
{
    if (l->get_type().is_same_unqualified_type(r->get_type()))
        return l->get_type();

    /* if one argument is a null-pointer constant, convert it to the
       type of the other one */
    if (l->is_npc())
        return r->get_type();
    if (r->is_npc())
        return l->get_type();

    assert(l->get_type().get_kind() == Type::k_Member);
    assert(r->get_type().get_kind() == Type::k_Member);

    Type lbase = l->get_type().get_class_type();
    Type rbase = r->get_type().get_class_type();
    Type lmem = l->get_type().get_member_type();
    Type rmem = r->get_type().get_member_type();
    Class_symbol* lclass = downcast<Class_symbol*>(lbase.get_type_symbol());
    Class_symbol* rclass = downcast<Class_symbol*>(rbase.get_type_symbol());

    /* we can cast "T Base::*" into "T Derived::*" */
    Type base;
    if (lclass == rclass || lclass->is_base_class_of(rclass))
        base = rbase.with_qualifiers(lbase);
    else if (rclass->is_base_class_of(lclass))
        base = lbase.with_qualifiers(rbase);
    else
        compile_error("comparing member pointers of distinct types");

    return base.make_member_type(get_merged_cv_type(lmem, rmem));
}

/** Do conversions for pointer arithmetic, to bring both to a common
    type. */
static void
do_pointer_arith_conversions(Expr_result* l, Expr_result* r)
{
    assert(l->get_type().get_kind() == Type::k_Pointer || l->is_npc());
    assert(r->get_type().get_kind() == Type::k_Pointer || r->is_npc());

    Type common = get_composite_pointer_type(l, r);
    l->convert_to(common);
    r->convert_to(common);
}

/** Do conversions for member pointer comparison, to bring both to a
    common type. */
static void
do_mptr_arith_conversions(Expr_result* l, Expr_result* r)
{
    assert(l->get_type().get_kind() == Type::k_Member || l->is_npc());
    assert(r->get_type().get_kind() == Type::k_Member || r->is_npc());

    Type common = get_composite_mptr_type(l, r);
    l->convert_to(common);
    r->convert_to(common);
}

/** Do the "usual arithmetic conversions", 5p9 */
static void
do_usual_conversions(Expr_result* l, Expr_result* r)
{
    assert(l->get_type().is_arithmetic_type() || l->get_type().is_enum_type());
    assert(r->get_type().is_arithmetic_type() || r->get_type().is_enum_type());

    /* If either operand is of type long double, the other shall be
     * converted to long double. */
    if (has_type(l, ldouble_type))
        r->convert_to(ldouble_type);
    else if (has_type(r, ldouble_type))
        l->convert_to(ldouble_type);
    /* Otherwise, if either operand is double, the other shall be
       converted to double. */
    else if (has_type(l, double_type))
        r->convert_to(double_type);
    else if (has_type(r, double_type))
        l->convert_to(double_type);
    /* Otherwise, if either operand is float, the other shall be
       converted to float. */
    // interesting. This means "int x = 20000000L + 1F" loses big.
    else if (has_type(l, float_type))
        r->convert_to(float_type);
    else if (has_type(r, float_type))
        l->convert_to(float_type);
    /* Otherwise, the integral promotions (4.5) shall be performed on
       both operands. */
    else {
        r->do_integral_promotions();
        l->do_integral_promotions();
        /* we support long long; I guess it belongs here */
        if (has_type(r, ullong_type))
            l->convert_to(ullong_type);
        else if (has_type(l, ullong_type))
            r->convert_to(ullong_type);
        else if (has_type(r, llong_type))
            l->convert_to(llong_type);
        else if (has_type(l, llong_type))
            r->convert_to(llong_type);
        /* Then, if either operand is unsigned long the other shall be
         * converted to unsigned long. */
        else if (has_type(r, ulong_type))
            l->convert_to(ulong_type);
        else if (has_type(l, ulong_type))
            r->convert_to(ulong_type);
        /* Otherwise, if one operand is a long int and the other
         * unsigned int, then if a long int can represent all the
         * values of an unsigned int, the unsigned int shall be
         * converted to a long int; otherwise both operands shall be
         * converted to unsigned long int. */
        // MACHINE: assume that uint doesn't fit into a long
        else if ((has_type(r, long_type) && has_type(l, uint_type))
                 || (has_type(l, uint_type) && has_type(r, long_type))) {
            r->convert_to(ulong_type);
            l->convert_to(ulong_type);
        }
        /* Otherwise, if either operand is long, the other shall be
           converted to long. */
        else if (has_type(r, long_type))
            l->convert_to(long_type);
        else if (has_type(l, long_type))
            r->convert_to(long_type);
        /* Otherwise, if either operand is unsigned, the other shall
         * be converted to unsigned. */
        else if (has_type(r, uint_type))
            l->convert_to(uint_type);
        else if (has_type(l, uint_type))
            r->convert_to(uint_type);
        /* [Note: otherwise, the only remaining case is that both
           operands are int] */
        else
            assert(has_type(r, int_type) && has_type(l, int_type));
    }
}

/***************************** Expr_annotator ****************************/

PUBLIC
Expr_annotator::Expr_annotator(Abstract_scope* scope, Source* source)
    : Paranoid_visitor<Expr_result>(source),
      Ptree_visitor<Expr_result>(source), current_scope(scope)
{ }

/** Generate tree for expression "*this". */
static Annotated<PtreeUnaryExpr>*
make_this_star(Type t)
{
    return new Annotated<PtreeUnaryExpr>(t, 0,
                                         make_static_leaf("*"),
                                         Ptree::List(make_this(t)));
}

/** Generate infix operator expression. */
static Annotated<PtreeInfixExpr>*
make_infix_expr(Type rt, Ptree* lhs, Ptree* op, Ptree* rhs)
{
    return new Annotated<PtreeInfixExpr>(rt, 0, lhs, Ptree::List(op, rhs));
}

/** Generate prefix operator expression. Exported, we need it in annotator.cpp.
    Maybe move this to Annotation? */
Annotated<PtreeUnaryExpr>*
make_prefix_expr(Type rt, Ptree* op, Ptree* arg)
{
    return new Annotated<PtreeUnaryExpr>(rt, 0, op, Ptree::List(arg));
}

/**************************** Binary operators ***************************/

/* Check whether t can be used in pointer arithmetics. Throws if not. */
static void
check_ptr_arith(Type t)
{
    Type b = t.get_basis_type();
    if (!b.is_complete())
        compile_error("pointer arithmetic with incomplete type");
    if (!b.is_object_type())
        compile_error("arithmetic with non-object type");
}

/** Visit comma operator. [lhs , rhs] Comma operators generate a
    different node than other infix operators, probably due to their
    different semantics. */
Expr_result
Expr_annotator::visit_comma(PtreeCommaExpr* e)
{
    expect_ptree(e->Second(), ',');

    Expr_result lhs = visit(e->First());
    Expr_result rhs = visit(e->Third());

    /* comma operator, 5.18 */
    if (!lhs.get_type().is_valid())
        compile_error("no type information for left operand in `,'");
    if (!rhs.is_value() && !rhs.is_function())
        compile_error("invalid right operand to `,'");

    if (lhs.get_type().get_kind() == Type::k_Userdef || rhs.get_type().get_kind() == Type::k_Userdef) {
        /* Overload resolution */
        Overload_resolver resolver(true);
        resolver.add_arg(lhs);
        resolver.add_arg(rhs);
        if (Class_symbol* csym = dynamic_cast<Class_symbol*>(lhs.get_type().get_type_symbol())) {
            if (Function_symbol* fsym = dynamic_cast<Function_symbol*>(csym->get_scope()->lookup_here(Symbol_name::COMMA_OPERATOR_NAME, false).untag))
                resolver.add_function(fsym, false);
        }
        if (Function_symbol* fsym = dynamic_cast<Function_symbol*>(current_scope->lookup_unqualified(Symbol_name::COMMA_OPERATOR_NAME).untag))
            resolver.add_function(fsym, false);

        // FIXME: Koenig lookup
        bool is_ambig;
        if (Overload_candidate* cand = resolver.get_best(&is_ambig)) {
            Annotated_funcall_maker afm(make_name(cand->fsig),
                                        cand->fsig->get_return_type());
            afm.add_arg(resolver.get_arg(0).get_tree());
            afm.add_arg(resolver.get_arg(1).get_tree());
            Expr_result result;
            result.set_value(afm.make_funcall(),
                             cand->fsig->get_return_type());
            return result;
        }
        if (is_ambig)
            compile_error("invocation of comma operator is ambigous");
    }

    rhs.set_tree(make_comma_expr(lhs.get_tree(), rhs.get_tree()));
    return rhs;
}

/** Generate annotated result for a built-in binary operator. */
Expr_result
Expr_annotator::process_binary_operator(Ptree* oper, Expr_result l, Expr_result r)
{
    if (oper->Eq("||")) {
        /* "||", 5.15 */
        l.convert_to_bool();
        r.convert_to_bool();
        return Expr_result(make_infix_expr(bool_type, l.get_tree(), oper, r.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq("&&")) {
        /* "&&", 5.14 */
        l.convert_to_bool();
        r.convert_to_bool();
        return Expr_result(make_infix_expr(bool_type, l.get_tree(), oper, r.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq('|')) {
        /* "|", 5.13 */
        l.do_std_conversions();
        r.do_std_conversions();
        do_usual_conversions(&l, &r);
        if (!l.get_type().is_int() || !r.get_type().is_int())
            compile_error("operands to binary `|' must be integers");
        return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq('^')) {
        /* "&", 5.12 */
        l.do_std_conversions();
        r.do_std_conversions();
        do_usual_conversions(&l, &r);
        if (!l.get_type().is_int() || !r.get_type().is_int())
            compile_error("operands to binary `^' must be integers");
        return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq('&')) {
        /* "&", 5.11 */
        l.do_std_conversions();
        r.do_std_conversions();
        do_usual_conversions(&l, &r);
        if (!l.get_type().is_int() || !r.get_type().is_int())
            compile_error("operands to binary `&' must be integers");
        return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq("==") || oper->Eq("!=")) {
        /* equality, 5.10 */
        l.do_std_conversions();
        r.do_std_conversions();
        bool two_npc = l.is_npc() && r.is_npc();
        if (!two_npc
            && (l.get_type().get_kind() == Type::k_Pointer || l.is_npc())
            && (r.get_type().get_kind() == Type::k_Pointer || r.is_npc()))
        {
            /* pointer/pointer or pointer/npc */
            do_pointer_arith_conversions(&l, &r);
        } else if (!two_npc
                   && (l.get_type().get_kind() == Type::k_Member || l.is_npc())
                   && (r.get_type().get_kind() == Type::k_Member || r.is_npc()))
        {
            /* member/member or member/npc */
            do_mptr_arith_conversions(&l, &r);
        } else {
            do_usual_conversions(&l, &r);
            if (!l.get_type().is_arithmetic_type() || !r.get_type().is_arithmetic_type())
                compile_error("invalid operands to relational operator");
        }
        assert(l.get_type().is_same_unqualified_type(r.get_type()));
        return Expr_result(make_infix_expr(bool_type, l.get_tree(), oper, r.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq('<') || oper->Eq('>') || oper->Eq("<=") || oper->Eq(">=")) {
        /* relational, 5.9 */
        l.do_std_conversions();
        r.do_std_conversions();
        bool two_npc = l.is_npc() && r.is_npc();
        if (!two_npc
            && (l.get_type().get_kind() == Type::k_Pointer || l.is_npc())
            && (r.get_type().get_kind() == Type::k_Pointer || r.is_npc()))
        {
            do_pointer_arith_conversions(&l, &r);
            /* ... and accept */
        } else {
            do_usual_conversions(&l, &r);
            if (!l.get_type().is_arithmetic_type() || !r.get_type().is_arithmetic_type())
                compile_error("invalid operands to relational operator");
        }
        assert(l.get_type().is_same_unqualified_type(r.get_type()));
        return Expr_result(make_infix_expr(bool_type, l.get_tree(), oper, r.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq("<<")) {
        /* "<<", 5.8 */
        l.do_std_conversions();
        r.do_std_conversions();
        l.do_integral_promotions();
        r.do_integral_promotions();
        if (!l.get_type().is_int() || !r.get_type().is_int())
            compile_error("operands to binary `<<' must be integers");
        return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq(">>")) {
        /* ">>", 5.8 */
        l.do_std_conversions();
        r.do_std_conversions();
        l.do_integral_promotions();
        r.do_integral_promotions();
        if (!l.get_type().is_int() || !r.get_type().is_int())
            compile_error("operands to binary `>>' must be integers");
        return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq('+')) {
        /* "+", 5.7. For addition, either both operands shall have
         * arithmetic or enumeration type, or one operand shall be a
         * pointer to a completely defined object type and the other
         * shall have integral or enumeration type. */
        l.do_std_conversions();
        r.do_std_conversions();
        l.do_integral_promotions();
        r.do_integral_promotions();
        if (l.get_type().get_kind() == Type::k_Pointer && r.get_type().is_int()) {
            /* ptr + int */
            check_ptr_arith(l.get_type());
            return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                               Expr_result::k_RValue);
        } else if (r.get_type().get_kind() == Type::k_Pointer && l.get_type().is_int()) {
            /* int + ptr. We swap l/r to the canonical form */
            check_ptr_arith(r.get_type());
            compile_warning("swapping sides of pointer addition", oper);
            return Expr_result(make_infix_expr(r.get_type(), r.get_tree(), oper, l.get_tree()),
                               Expr_result::k_RValue);
        } else if (r.get_type().is_arithmetic_type() && l.get_type().is_arithmetic_type()) {
            /* arithmetics */
            do_usual_conversions(&l, &r);
            assert((l.get_type().is_int() && r.get_type().is_int())
                   || (l.get_type().is_float() && r.get_type().is_float()));
            return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                               Expr_result::k_RValue);
        } else
            compile_error("invalid arguments to binary `+'");
    } else if (oper->Eq('-')) {
        l.do_std_conversions();
        r.do_std_conversions();
        l.do_integral_promotions();
        r.do_integral_promotions();
        if (l.get_type().get_kind() == Type::k_Pointer && r.get_type().get_kind() == Type::k_Pointer) {
            /* ptr - ptr */
            do_pointer_arith_conversions(&l, &r);
            check_ptr_arith(l.get_type());
            return Expr_result(make_infix_expr(ptrdiff_type, l.get_tree(), oper, r.get_tree()),
                               Expr_result::k_RValue);
        } else if (l.get_type().get_kind() == Type::k_Pointer && r.get_type().is_int()) {
            /* ptr - int */
            check_ptr_arith(l.get_type());
            return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                               Expr_result::k_RValue);
        } else if (r.get_type().is_arithmetic_type() && l.get_type().is_arithmetic_type()) {
            /* arithmetics */
            do_usual_conversions(&l, &r);
            assert((l.get_type().is_int() && r.get_type().is_int())
                   || (l.get_type().is_float() && r.get_type().is_float()));
            return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                               Expr_result::k_RValue);
        } else
            compile_error("invalid arguments to binary `-'");
    } else if (oper->Eq('*')) {
        /* "*", 5.6: arithmetic or enumeration type. do_usual_conversions
           does integral promotions, i.e., it resolves enums */
        do_usual_conversions(&l, &r);
        if ((l.get_type().is_int() && r.get_type().is_int())
            || (l.get_type().is_float() && r.get_type().is_float()))
            return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                               Expr_result::k_RValue);
        else
            compile_error("invalid arguments to binary `*'");
    } else if (oper->Eq('/')) {
        /* "/", 5.6: arithmetic or enumeration type */
        do_usual_conversions(&l, &r);
        if ((l.get_type().is_int() && r.get_type().is_int())
            || (l.get_type().is_float() && r.get_type().is_float()))
            return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                               Expr_result::k_RValue);
        else
            compile_error("invalid arguments to binary `/'");
    } else if (oper->Eq('%')) {
        /* "%", 5.6: integer type */
        do_usual_conversions(&l, &r);
        if (l.get_type().is_int() && r.get_type().is_int())
            return Expr_result(make_infix_expr(l.get_type(), l.get_tree(), oper, r.get_tree()),
                               Expr_result::k_RValue);
        else
            compile_error("invalid arguments to binary `%'");
    } else
        bogus_ptree_error("den Operator kenn ich noch nicht", oper);
}

/** Visit infix operator.
    [ lhs oper rhs ] */
PUBLIC Expr_result
Expr_annotator::visit_infix (PtreeInfixExpr *p)
{
    Expr_result l = visit(p->First());
    Expr_result r = visit(p->Third());

    // FIXME: this is a hack until we have overload resolution
    if ((l.get_type().get_kind() != Type::k_Userdef || l.get_type().is_enum_type())
        && (r.get_type().get_kind() != Type::k_Userdef || r.get_type().is_enum_type()))
        return process_binary_operator(p->Second(), l, r);
    else
        compile_error("FIXME: user-defined operator geht noch nicht");
    return Expr_result();
}

/************************* Atoms (literal, names) ************************/

/** Visit a leaf, i.e.\ literal. */
PUBLIC Expr_result
Expr_annotator::visit_leaf (Leaf* l)
{
    using namespace std;        // string functions

    /* Bummer. Have to parse the leaf *again*. */
    const char* c = l->ToString();
    Type t;
    if ((*c >= '0' && *c <= '9') || *c == '.') {
        /* a number */
        if ((c[0] == '0' && (c[1] == 'x' || c[1] == 'X')) || strpbrk(c, ".eE") == 0) {
            /* integer. int if decimal, uint if hex/oct */
            // MACHINE: hex/oct literals are int if they fit into one
            bool is_uns = strpbrk(c, "uU") || (c[0] == '0' && c[strspn(c, "0")] != 0);
            bool is_long = strpbrk(c, "lL");
            t = is_uns ? is_long ? ulong_type : uint_type : is_long ? long_type : int_type;
        } else {
            /* float */
            if (strpbrk(c, "fF"))
                t = float_type;
            else if (strpbrk(c, "lL"))
                t = ldouble_type;
            else
                t = double_type;
        }
    } else if (*c == '\'') {
        /* a character */
        t = char_type;
    } else if (*c == '\"') {
        /* a string */
        // FIXME: this makes literals come out as "char[]", not "const char[]"
        t = char_type.make_array_type(0);
    } else if (*c == 'l' || *c == 'L') {
        /* long string/char. OpenC++ doesn't do these */
        if (c[1] == '\'')
            t = wchar_type;
        else if (c[1] == '"')
            // FIXME: this makes literals come out as "wchar_t[]", not "const wchar_t[]"
            t = wchar_type.make_array_type(0);
        else
            bogus_ptree_error("strange long thing", l);
            // return visit_name(l);
    } else {
        bogus_ptree_error("unknown leaf type", l);
        // return visit_name(l);
    }

    return Expr_result(new Annotated<Leaf>(t, 0, *l), Expr_result::k_RValue);
}

/** Visit name, i.e.\ identifier. Parameter may be LeafName (unqual)
    or PtreeName (qualified) */
PUBLIC Expr_result
Expr_annotator::visit_name (Ptree* p)
{
    if (p->IsLeaf() && (p->Eq("true") || p->Eq("false")))
        return Expr_result(new Annotated<Leaf>(bool_type, 0, *downcast<Leaf*>(p)),
                           Expr_result::k_RValue);

    /* look up symbol */
    Symbol_pair sp = Symbol_name(p, current_scope, false).lookup_for_use(false);
    if (!sp)
        compile_error("unknown symbol `" + std::string(p->ToString()) + "'");

    if (sp.untag->get_kind() == Symbol::k_Variable) {
        /* A variable */
        Variable_symbol* vsym = downcast<Variable_symbol*>(sp.untag);
        Type t = vsym->get_type().sans_reference();
        Expr_result::Kind k = (vsym->has_address()
                               ? Expr_result::k_LValue
                               : Expr_result::k_RValue);
        Ptree* name_tree = make_name(vsym);
        if (vsym->is_member_variable()) {
            /* Member variable */
            Type this_type = current_scope->get_this_type();
            if (!this_type.is_valid())
                compile_error("attempt to access member variable without an object");

            Class_symbol* this_class = downcast<Class_symbol*>(this_type.get_type_symbol());
            if (vsym->get_class() != this_class && !vsym->get_class()->is_unique_base_class_of(this_class))
                compile_error("attempt to access member variable of different class");
            if (this_type.is_qualified(Type::q_Const) && (vsym->get_storage_class() != s_Mutable))
                t.add_qualifier(Type::q_Const);
            return Expr_result(new Annotated<PtreeDotMemberExpr>(t, vsym,
                                                                 make_this_star(this_type),
                                                                 Ptree::List(make_static_leaf("."),
                                                                             name_tree)),
                               k);
        } else {
            return Expr_result(name_tree, t, k);
        }
    } else if (sp.untag->get_kind() == Symbol::k_Function) {
        /* A function. No Koenig lookup here. Koenig lookup is *only*
           used when an unqualified name is used on the LHS of a
           function call, i.e. "foo(x)". It is *not* used if the LHS
           is something more elaborate than that, e.g. "(foo)(x)" or
           even "(1,foo)(x)" */
        Function_symbol* fs = downcast<Function_symbol*>(sp.untag);
        Function_signature* fsig = 0;
        if (!fs->is_overloaded())
            fsig = fs->get_nonoverloaded_signature();
        if (fsig && fsig->get_storage_specifier() != s_Member) {
            /* non-overloaded function, we know the type */
            return Expr_result(make_name(fsig), Expr_result::k_RValue);
        } else {
            /* overloaded or member function. defer type inference. */
            if (p->IsLeaf())
                return Expr_result(new Annotated<LeafName>(Type(), sp.untag, *downcast<LeafName*>(p)),
                                   fs);
            else
                return Expr_result(new Annotated<PtreeName>(Type(), sp.untag, *downcast<PtreeName*>(p)),
                                   fs);
        }
    } else {
        compile_error("I don't understand this symbol `" + std::string(p->ToString()) + "' at this place");
    }
}

/** Visit "this" node. */
PUBLIC Expr_result
Expr_annotator::visit_this(LeafThis* p)
{
    expect_ptree(p, "this");
    Type t = current_scope->get_this_type();
    if (!t.is_valid())
        compile_error("`this' is not valid here");

    return Expr_result(make_this(t), Expr_result::k_RValue);
}

/****************************** Parentheses ******************************/

/** Visit parenthesized expression. These have no semantics, and don't
    appear in output. */
PUBLIC Expr_result
Expr_annotator::visit_paren (PtreeParenExpr* e)
{
    expect_ptree(e->First(), '(');
    expect_ptree(e->Third(), ')');
    return visit(e->Second());
}

/*************************** Postfix operators ***************************/

/** Process a postfix expression. Input is
    | PtreePostfixExpr
    |   expression
    |   ++ or -- */
PUBLIC Expr_result
Expr_annotator::visit_postfix(PtreePostfixExpr* e)
{
    Ptree* oper_tree = e->Second();
    Expr_result arg = visit(e->First());

    if (arg.get_type().get_kind() == Type::k_Userdef) {
        /* user defined operator */
        Leaf zero_leaf((char*)"0", 1);
        Overload_resolver resolver(true /* is operator */);
        resolver.add_arg(arg);
        resolver.add_arg(Expr_result(new Annotated<Leaf>(int_type, 0, zero_leaf),
                                     Expr_result::k_RValue));

        Class_symbol* csym = dynamic_cast<Class_symbol*>(arg.get_type().get_type_symbol());
        const char* opname = Symbol_name::get_operator_name(oper_tree);
        assert(opname);

        /* generate candidate list. */
        if(csym) {
            Symbol_pair p = csym->get_scope()->lookup_here(opname, false);
            Function_symbol* fsym = dynamic_cast<Function_symbol*>(p.untag);
            if (fsym)
                resolver.add_function(fsym, false);
        }

        // FIXME: Koenig lookup?
        Symbol_pair p = current_scope->lookup_unqualified(opname);
        if (Function_symbol* fsym = dynamic_cast<Function_symbol*>(p.untag))
            resolver.add_function(fsym, false);

        // FIXME: "do not have the same parameter type list as any
        // non-template non-member candidate". I think this one's not needed;
        // it only affects operations with enums, but then the conversions
        // will be worse than with the user-defined operator
        if (oper_tree->Eq("++")) {
            resolver.add_builtin_incdec(true);
        } else if (oper_tree->Eq("--")) {
            resolver.add_builtin_incdec(false);
        } else {
            bogus_ptree_error("expected ++ or --", e);
        }

        bool is_ambig;
        Overload_candidate* cand = resolver.get_best(&is_ambig);
        if (is_ambig)
            compile_error("call to postfix operator `" + std::string(oper_tree->ToString()) + "' is ambiguous");
        if (cand) {
            if (!cand->fsig->is_builtin()) {
                // it's a user-defined operator; call it
                Expr_result result;
                Annotated_funcall_maker afm(make_name(cand->fsig),
                                            cand->fsig->get_return_type());
                afm.add_arg(resolver.get_arg(0).get_tree());
                afm.add_arg(resolver.get_arg(1).get_tree());
                result.set_value(afm.make_funcall(),
                                 cand->fsig->get_return_type());
                return result;
            } else {
                arg = resolver.get_arg(0);
            }
        }
    }

    /* when we're here, it is a builtin operator */
    if (oper_tree->Eq("++")) {
        /* postfix ++: arithmetic, or pointer to complete object type;
           modifyable lvalue */
        if (arg.get_type().is_arithmetic_type()) {
            /* ok */
        } else if (arg.get_type().get_kind() == Type::k_Pointer) {
            if (!arg.get_type().get_basis_type().is_complete())
                compile_error("postfix `++' applied to incomplete type");
        } else
            compile_error("postfix `++' applied to invalid type");
        if (!arg.is_modifyable_lvalue())
            compile_error("postfix `++' needs modifyabla lvalue");
        return Expr_result(new Annotated<PtreePostfixExpr>(arg.get_type().get_unqualified_type(),
                                                           0 /* symbol */,
                                                           arg.get_tree(),
                                                           Ptree::List(oper_tree)),
                           Expr_result::k_RValue);
    } else if (oper_tree->Eq("--")) {
        /* postfix --: arithmetic, or pointer to complete object type, but
           not bool; modifyable lvalue */
        if (arg.get_type().is_arithmetic_type()) {
            if (arg.get_type().is_same_unqualified_type(bool_type))
                compile_error("postfix `--' applied to `bool'");
        } else if (arg.get_type().get_kind() == Type::k_Pointer) {
            if (!arg.get_type().get_basis_type().is_complete())
                compile_error("postfix `--' applied to incomplete type");
        } else
            compile_error("postfix `--' applied to invalid type");
        if (!arg.is_modifyable_lvalue())
            compile_error("postfix `--' needs modifyabla lvalue");
        return Expr_result(new Annotated<PtreePostfixExpr>(arg.get_type().get_unqualified_type(),
                                                           0 /* symbol */,
                                                           arg.get_tree(),
                                                           Ptree::List(oper_tree)),
                           Expr_result::k_RValue);
    } else {
        bogus_ptree_error("bogus postfix operator", e);
    }
}

/**************************** Unary Operators ****************************/

/** Predicate for unary "*" operator. There is one "operator*(T*)" for
    every function and object pointer. */
static Type
unary_deref_predicate(Type t)
{
    if (t.get_kind() == Type::k_Pointer) {
        Type b = t.get_basis_type();
        if (b.is_object_type() || b.get_kind() == Type::k_Function)
            return make_unary_function_type(t, b.make_reference_type());
    }
    return Type();
}

/** Predicate for unary "+" operator. There is one "operator+(T)" for
    every pointer and promoted arithmetic type. */
static Type
unary_plus_predicate(Type t)
{
    if (t.get_kind() == Type::k_Pointer) {
        return make_unary_function_type(t, t);
    } else if (t.is_arithmetic_type() || t.is_enum_type()) {
        Type p = t.get_promoted_integer();
        return make_unary_function_type(p, p);
    }
    return Type();
}

/** Predicate for unary "-" operator. There is one "operator-(T)" for
    every promoted arithmetic type. */
static Type
unary_minus_predicate(Type t)
{
    if (t.is_arithmetic_type() || t.is_enum_type()) {
        Type p = t.get_promoted_integer();
        return make_unary_function_type(p, p);
    }
    return Type();
}

/** Predicate for unary "~" operator. There is one for every promoted
    integral type. */
static Type
unary_bitnot_predicate(Type t)
{
    if (t.is_int() || t.is_enum_type()) {
        Type p = t.get_promoted_integer();
        return make_unary_function_type(p, p);
    }
    return Type();
}

// static Type
// cast_to_enum_predicate(Type t)
// {
//     if (t.is_int() || t.is_enum_type())
//         return make_unary_function_type(t, t);
//     return Type();
// }

/** Process unary builtin operator.
    \param oper  the operator. Must be a leaf containing the operator.
    \param arg   visited parameter */
PRIVATE Expr_result
Expr_annotator::process_unary_operator(Ptree* oper, Expr_result arg)
{
    /* unary operators, 5.3.1 */
    if (oper->Eq('*')) {
        arg.do_std_conversions();
        if (arg.get_type().get_kind() != Type::k_Pointer)
            compile_error("operand to `*' must be pointer");
        Type r = arg.get_type().get_basis_type();
        if (r.is_void())
            compile_error("can't dereference a `void*'");
        return Expr_result(make_prefix_expr(r, oper, arg.get_tree()), Expr_result::k_LValue);
    } else if (oper->Eq('&')) {
        /* unary '&': the special case (argument is qualified-id) has
           already been handled. */
        if (!arg.is_value()) {
            /* overload resolution, "&(overloaded-function-name)",
               or even "&(expr, overloaded-function-name)".
               but not "&(obj->function)". */
            if (!arg.is_function())
                compile_error("invalid argument to `&'");
            return arg;
        }

        if (arg.get_type().get_kind() == Type::k_Function || arg.is_lvalue()) {
            return Expr_result(make_prefix_expr(arg.get_type().make_pointer_type(),
                                                oper, arg.get_tree()),
                               Expr_result::k_RValue);
        } else {
            compile_error("invalid argument to unary `&'");
        }
    } else if (oper->Eq('+')) {
        /* unary '+': arithmetic, enum or pointer */
        arg.do_std_conversions();
        arg.do_integral_promotions();
        if (arg.get_type().get_kind() == Type::k_Pointer || arg.get_type().is_arithmetic_type())
            return Expr_result(make_prefix_expr(arg.get_type(), oper, arg.get_tree()),
                               Expr_result::k_RValue);
        else
            compile_error("invalid argument to unary `+'");
    } else if (oper->Eq('-')) {
        /* unary '-': arithmetic or enum */
        arg.do_std_conversions();
        arg.do_integral_promotions();
        if (arg.get_type().is_int() || arg.get_type().is_float())
            return Expr_result(make_prefix_expr(arg.get_type(), oper, arg.get_tree()),
                               Expr_result::k_RValue);
        else
            compile_error("invalid operand to unary `-'");
    } else if (oper->Eq('!')) {
        /* unary '!': bool */
        arg.convert_to_bool();
        return Expr_result(make_prefix_expr(bool_type, oper, arg.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq('~')) {
        /* unary '~': integer or enum */
        arg.do_std_conversions();
        arg.do_integral_promotions();
        if (!arg.get_type().is_int())
            compile_error("invalid operand to unary `~'");
        return Expr_result(make_prefix_expr(arg.get_type(), oper, arg.get_tree()),
                           Expr_result::k_RValue);
    } else if (oper->Eq("++")) {
        /* pre-increment (5.3.2): modifyable lvalue, arithmetic or
           pointer */
        if (arg.get_type().get_kind() == Type::k_Pointer) {
            if (!arg.get_type().get_basis_type().is_complete())
                compile_error("`++' applied to pointer to incomplete type");
        } else if (!arg.get_type().is_arithmetic_type())
            compile_error("`++' applied to wrong type");
        if (arg.is_modifyable_lvalue())
            return Expr_result(make_prefix_expr(arg.get_type(), oper, arg.get_tree()),
                               Expr_result::k_LValue);
        else
            compile_error("`++' only works for modifyable lvalues");
    } else if (oper->Eq("--")) {
        /* pre-decrement (5.3.2): modifyable lvalue, arithmetic or
           pointer, but not bool */
        if (arg.get_type().get_kind() == Type::k_Pointer) {
            if (!arg.get_type().get_basis_type().is_complete())
                compile_error("`--' applied to pointer to incomplete type");
        } else if (!arg.get_type().is_arithmetic_type() || arg.get_type().is_same_unqualified_type(bool_type))
            compile_error("`--' applied to wrong type");
        if (arg.is_modifyable_lvalue())
            return Expr_result(make_prefix_expr(arg.get_type(), oper, arg.get_tree()),
                               Expr_result::k_LValue);
        else
            compile_error("`--' only works for modifyable lvalues");
    } else {
        bogus_ptree_error("unknown operator", oper);
    }
}

/** Visit unary operator. Input is [op arg]. */
PUBLIC Expr_result
Expr_annotator::visit_unary (PtreeUnaryExpr* e)
{
    Ptree* oper_tree = e->First();
    Ptree* arg_tree  = e->Second();

    /* Special case first: if parameter is qualified-id, it might be a
       pointer-to-member literal */
    if (oper_tree->Eq('&') && ptree_is_name(arg_tree)) {
        Symbol_name name(arg_tree, current_scope, false);
        if (name.is_qualified()) {
            /* if it's a qualified name, it can't be a leaf. */
            assert(!arg_tree->IsLeaf());

            Symbol* p = name.lookup_for_use(false).untag;
            if (!p)
                compile_error("unknown identifier `" + std::string(arg_tree->ToString()) + "'");

            /* relevant cases:
               - non-member variable ("&normal::variable" is handled by normal code)
               - possibly overloaded function
               If it's neither of these cases, fall through to normal handler */
            if (Variable_symbol* var = dynamic_cast<Variable_symbol*>(p)) {
                if (var->is_member_variable())
                    return Expr_result(make_prefix_expr(var->get_class()->get_type().make_member_type(var->get_type()),
                                                        e->First(),
                                                        make_name(var)),
                                       Expr_result::k_RValue);
            } else if (Function_symbol* fsym = dynamic_cast<Function_symbol*>(p)) {
                if (fsym->is_overloaded()) {
                    return Expr_result(new Annotated<PtreeName>(Type(),
                                                                fsym,
                                                                *downcast<PtreeName*>(arg_tree)),
                                       fsym);
                } else {
                    Function_signature* fsig = fsym->get_nonoverloaded_signature();
                    return Expr_result(new Annotated<PtreeName>(fsig->get_pointer_type(),
                                                                fsig,
                                                                *downcast<PtreeName*>(arg_tree)),
                                       Expr_result::k_RValue);
                }
            }
        }
    }

    /* We now return to our scheduled operator evaluation. */
    Expr_result arg = visit(arg_tree);

    if (arg.get_type().get_kind() == Type::k_Userdef) {
        /* If the parameter has user-defined type, we must do
           operator overloading */
        Ptree* oper        = e->First();
        Class_symbol* csym = dynamic_cast<Class_symbol*>(arg.get_type().get_type_symbol());

        Overload_resolver resolver(true);
        resolver.add_arg(arg);

        const char* opname = Symbol_name::get_operator_name(oper);
        assert(opname);

        /* generate candidate list. */

        /* If T1 is a class type, the set of member candidates is the
         * result of the qualified lookup of T1::operator@
         * (13.3.1.1.1); otherwise, the set of member candidates is
         * empty. */
        if(csym) {
            Symbol_pair p = csym->get_scope()->lookup_here(opname, false);
            Function_symbol* fsym = dynamic_cast<Function_symbol*>(p.untag);
            if (fsym)
                resolver.add_function(fsym, false);
        }

        /* The set of non-member candidates is the result of the
         * unqualified lookup of operator@ in the context of the
         * expression according to the usual rules for name lookup in
         * unqualified function calls (3.4.2) except that all member
         * functions are ignored. However, if no operand has a class
         * type, only those non-member functions in the lookup set
         * that have a first parameter of type T1 or reference to
         * (possibly cv-qualified) T1 , when T1 is an enumeration
         * type, or (if there is a right operand) a second parameter
         * of type T2 or reference to (possibly cv-qualified) T2 ,
         * when T2 is an enumeration type, are candidate functions. */
        // FIXME: Koenig lookup?
        Symbol_pair p = current_scope->lookup_unqualified(opname);
        if (Function_symbol* fsym = dynamic_cast<Function_symbol*>(p.untag))
            resolver.add_function(fsym, false);

        // FIXME: "do not have the same parameter type list as any
        // non-template non-member candidate". I think this one's not needed;
        // it only affects operations with enums, but then the conversions
        // will be worse than with the user-defined operator
        if (oper->Eq("++")) {
            resolver.add_builtin_incdec(true);
        } else if (oper->Eq("--")) {
            resolver.add_builtin_incdec(false);
        } else if (oper->Eq('*')) {
            resolver.add_builtin_unary_ops(unary_deref_predicate);
        } else if (oper->Eq('&')) {
            // there are no built-in candidates
        } else if (oper->Eq('+')) {
            resolver.add_builtin_unary_ops(unary_plus_predicate);
        } else if (oper->Eq('-')) {
            resolver.add_builtin_unary_ops(unary_minus_predicate);
        } else if (oper->Eq('!')) {
            /* bool operator!(bool) */
            resolver.add_signature(Function_signature::make_builtin(make_unary_function_type(bool_type, bool_type)));
        } else if (oper->Eq('~')) {
            resolver.add_builtin_unary_ops(unary_bitnot_predicate);
        } else {
            assert(0);
        }

        bool is_ambig;
        Overload_candidate* cand = resolver.get_best(&is_ambig);
        if (is_ambig)
            compile_error("call to operator `" + std::string(oper->ToString()) + "' is ambiguous");
        if (cand) {
            if (!cand->fsig->is_builtin()) {
                // it's a user-defined operator; call it
                Expr_result result;
                result.set_value(make_unary_funcall(make_name(cand->fsig),
                                                    cand->fsig->get_return_type(),
                                                    resolver.get_arg(0).get_tree()),
                                 cand->fsig->get_return_type());
                return result;
            } else {
                arg = resolver.get_arg(0);
            }
        }
    }

    return process_unary_operator(e->First(), arg);
}

/********************************* Delete ********************************/

/** Predicate for builtin "->" operator, and for "delete". Those need
    a pointer to object on the left-hand side. The return type is
    irrelevant for overload resolution. */
static Type
unary_delete_or_arrow_predicate(Type t)
{
    if (t.get_kind() == Type::k_Pointer && t.get_basis_type().is_object_type())
        return make_unary_function_type(t, void_type);
    return Type();
}

/** "Delete" expression. */
PUBLIC Expr_result
Expr_annotator::visit_delete(PtreeDeleteExpr* pde)
{
    /* possible forms:
         [:: delete expr]
         [:: delete [ ] expr]
         [delete expr]
         [delete [ ] expr] */
    Ptree* expr;
    Ptree* p = pde;
    bool is_global = false, is_array = false;
    if (p->First()->Eq("::")) {
        is_global = true;
        p = p->Cdr();
    }

    expect_ptree(p->First(), "delete");
    if (p->Second()->Eq('[')) {
        expect_ptree(p->Third(), ']');
        expr = p->Nth(3);
        is_array = true;
    } else {
        expr = p->Second();
    }

    /* okay, we know how it looks. Solve it. */
    Expr_result arg = visit(expr);

    /* Convert class types to pointer */
    if (arg.get_type().is_class_type()) {
        /* FIXME: this isn't perfect, but it's simple. When the class
           has two conversion functions, but only one of them is
           viable, we would call that one, although 5.3.5p1 says the
           program is ill-formed:
             The operand shall have a pointer type, or a class type
             having a single conversion function to a pointer type.
           This rules out
             struct a { operator int*(); operator int*() const; };
             const a the_a;
             delete the_a;
           which we happily accept. */
        Overload_resolver resolver(true);
        resolver.add_arg(arg);
        resolver.add_builtin_unary_ops(unary_delete_or_arrow_predicate);

        bool is_ambig;
        Overload_candidate* cand = resolver.get_best(&is_ambig);
        if (is_ambig)
            compile_error("call to operator delete is ambiguous");
        if (!cand)
            compile_error("no possible conversion to pointer for operator delete");

        // Overload_resolver will have done the call for us
        arg = resolver.get_arg(0);
    }

    /* argument must now be a pointer */
    if (arg.get_type().get_kind() != Type::k_Pointer || !arg.get_type().get_basis_type().is_object_type())
        compile_error("invalid argument to operator delete");

    // FIXME: look up the actual "delete" to use
    Symbol* delete_sym = 0;

    /* build return tree */
    if (is_array) {
        /* [delete-symbol, void] PtreeDeleteExpr
             delete
             [
             ]
             expr */
        Annotated<PtreeDeleteExpr>* tree =
            new Annotated<PtreeDeleteExpr>(void_type,
                                           delete_sym,
                                           p->First(),
                                           Ptree::List(p->Second(),
                                                       p->Third(),
                                                       arg.get_tree()));
        return Expr_result(tree, Expr_result::k_RValue);
    } else {
        /* [delete-symbol, void] PtreeDeleteExpr
             delete
             expr */
        return Expr_result(new Annotated<PtreeDeleteExpr>(void_type,
                                                          delete_sym,
                                                          p->First(),
                                                          Ptree::List(arg.get_tree())),
                           Expr_result::k_RValue);
    }
}

/********************************** New **********************************/

/** Visit "new" operator. */
PUBLIC Expr_result
Expr_annotator::visit_new(PtreeNewExpr* p_)
{
    Ptree* p = p_;
    /*
      [new null [type declarator]]
      [new null [type declarator] [( init-list )]]
      [new [( args )] [type decl]]
      [:: new ...]
     */
    bool global = false;
    if (p->First()->Eq("::")) {
        p = p->Cdr();
        global = true;
    }

    expect_ptree(p->First(), "new");

    /* figure out type */
    Ptree* type_tree = p->Third();
    Type t = parse_type(type_tree->First(), current_scope, 0, false);
    if (!parse_abstract_declarator(type_tree->Second(), current_scope, &t))
        compile_error("invalid type for `new'");

    /* figure out basis type */
    Type basis_type = t.sans_array();
    if (!t.is_object_type())
        compile_error("non-object type for `new'");
    const char* op_name = (t.get_kind() == Type::k_Array ? Symbol_name::ANEW_OPERATOR_NAME : Symbol_name::NEW_OPERATOR_NAME);

    Overload_resolver resolver(false);
    Overload_candidate* cand = 0;

    resolver.add_arg(make_sizeof_expr(basis_type));  // FIXME: wrong for arrays
    if (p->Second()) {
        Ptree* args = p->Second();
        expect_ptree(args->Car(), '(');
        expect_ptree(args->Third(), ')');
        add_parms_from_arglist(&resolver, args->Second());
    }
    if (!global && basis_type.is_class_type()) {
        /* look up in class scope */
        Function_symbol* fsym = dynamic_cast<Function_symbol*>(downcast<Class_symbol*>(basis_type.get_type_symbol())->get_scope()->lookup_here(op_name, false).untag);
        if (fsym) {
            resolver.add_function(fsym, true);

            bool is_ambig;
            cand = resolver.get_best(&is_ambig);
            if (is_ambig)
                compile_error ("ambiguous call to operator new for type " + basis_type.get_human_readable_type());
        }
    }

    if (!cand) {
        Function_symbol* fsym = dynamic_cast<Function_symbol*>(current_scope->get_global_scope()->lookup_here(op_name, false).untag);
        if (!fsym)
            compile_error("huh? no operator new declared");
        resolver.add_function(fsym, true);

        bool is_ambig;
        cand = resolver.get_best(&is_ambig);
        if (is_ambig)
            compile_error("ambiguous call to ::operator new for type " + basis_type.get_human_readable_type());
    }

    if (!cand)
        compile_error("no matching function to call for this operator new expression");

    /* output tree:
         [function, Type] PtreeNewExpr
           new
           ( args 1..N )
           NonLeaf
             [nothing, Type] name
             PtreeDeclarator
               null
           [ctor, Type] NonLeaf
             (
             args
             ) */
    Ptree* init = 0;
    if (p->Length() > 3)
        init = Init_handler(current_scope, p->Nth(3), false).process_initializer(t);

    Ptree* call = 0;
    if (resolver.get_arg_count() > 1) {
        Ptree* list = 0;
        for (unsigned i = 1; i < resolver.get_arg_count(); ++i) {
            if (list) {
                Ptree::Snoc(list, make_static_leaf(","));
                Ptree::Snoc(list, resolver.get_arg(i).get_tree());
            } else {
                list = Ptree::List(resolver.get_arg(i).get_tree());
            }
        }
        call = Ptree::List(make_static_leaf("("), list, make_static_leaf(")"));
    }

    Encoding tmp_enc;
    Ptree* tail = Ptree::List(call,
                              Ptree::List(make_name(t.get_encoded_type(), t, 0),
                                          new PtreeDeclarator(Ptree::List(0), tmp_enc)));
    if (init)
        Ptree::Snoc(tail, init);

    return Expr_result(new Annotated<PtreeNewExpr>(t.get_kind() == Type::k_Array ? t.get_basis_type().make_pointer_type() : t.make_pointer_type(),
                                                   cand->fsig,
                                                   p->First() /* "new" */,
                                                   tail),
                       Expr_result::k_RValue);
}

/********************************* Sizeof ********************************/

/** Make a "sizeof" expression for type t (i.e. "sizeof(T)"). */
static Expr_result
make_sizeof_expr(Type t)
{
    if (!t.is_valid() || !t.is_complete() || t.get_kind() == Type::k_Function)
        compile_error("invalid type argument to `sizeof'");

    Annotated<PtreeSizeofExpr>* ex =
        new Annotated<PtreeSizeofExpr>(size_type, 0,
                                       make_static_leaf("sizeof"),
                                       Ptree::List(make_static_leaf("("),
                                                   make_name(t.get_encoded_type(), t, 0),
                                                   make_static_leaf(")")));
    return Expr_result(ex, Expr_result::k_RValue);
}

/** Visit sizeof expression. Those can take both expressions and types. */
PUBLIC Expr_result
Expr_annotator::visit_sizeof(PtreeSizeofExpr* e)
{
    /* sizeof expr  => [sizeof expr]
       sizeof(var)  => [sizeof ( [var [PtreeDeclarator:null]] )]
       sizeof(x+y)  => [sizeof [( [x + y] )]]
       sizeof(int)  => [sizeof ( [[int] [null]] )]
       sizeof(type) => [sizeof ( [type [null]] )]
       sizeof(::t)  => [sizeof ( [[:: t] [null]] )]
       sizeof(t*)   => [sizeof ( [t [*]] )]
       sizeof(*p)   => [sizeof [( [* p] )]]

       It seems general expressions are handled correctly. The only
       problematic case seems to be "sizeof(name)" where the name can
       either be a symbol or a type. Dammit, another try-and-retry case.

       No matter how the input looks, we generate
         [no symbol, size_type] PtreeSizeofExpr
           sizeof
           (
           [no symbol, TYPE] TYPE
           )
    */

    expect_ptree(e->First(), "sizeof");
    if (e->Length() == 4) {
        /* arg is type or expression */
        expect_ptree(e->Second(), '(');
        expect_ptree(e->Nth(3), ')');

        Ptree* arg = e->Third();

        /* try to interpret it as a type */
        if (!arg->Second() || (!arg->Second()->IsLeaf() && !arg->Second()->First())) {
            try {
                return make_sizeof_expr(parse_type(arg->First(), current_scope, 0, false));
            }
            catch(...) { }

            /* must be a name */
            Symbol* sym = Symbol_name(arg->First(), current_scope, false).lookup_for_use(false).untag;
            if (Type_symbol* tsym = dynamic_cast<Type_symbol*>(sym))
                return make_sizeof_expr(tsym->get_type());
            else if (Variable_symbol* vsym = dynamic_cast<Variable_symbol*>(sym))
                return make_sizeof_expr(visit_name(arg->First()).get_type());
            else
                compile_error("invalid argument to sizeof");
        }

        /* when we're here, it's a real type */
        Type t = parse_type(arg->First(), current_scope, 0, false);
        if (parse_abstract_declarator(arg->Second(), current_scope, &t)) {
            return make_sizeof_expr(t);
        } else {
            compile_error("invalid type for sizeof");
        }
    } else if (e->Length() == 2) {
        /* arg is an expression */
        return make_sizeof_expr(visit(e->Second()).get_type());
    } else {
        bogus_ptree_error("don't understand this sizeof", e);
    }
}

/** Visit throw expression. */
PUBLIC Expr_result
Expr_annotator::visit_throw(PtreeThrowExpr* p)
{
    expect_ptree(p->First(), "throw");

    Ptree* ex_tree;
    if (!p->Second()) {
        /* rethrow expression: "[throw null]" */
        ex_tree = 0;
    } else {
        /* throw expression: "[throw expr]" */
        Expr_result r = visit(p->Second());
        if (r.get_type().is_void())
            compile_error("throw void is not allowed");
        r.convert_to_pointer();
        r.convert_to_fpointer();
        r.convert_to_qual(r.get_type().get_unqualified_type());
        ex_tree = r.get_tree();
    }

    return Expr_result(new Annotated<PtreeThrowExpr>(void_type, 0,
                                                     p->First(),
                                                     Ptree::List(ex_tree)),
                       Expr_result::k_RValue);
}

/**************************** Member reference ***************************/

/** Process an operation of form "lhs . rhs_tree". The rhs_tree is a name. */
PRIVATE Expr_result
Expr_annotator::process_member_access(Expr_result lhs, Ptree* rhs_tree)
{
    Class_symbol* csym = downcast<Class_symbol*>(lhs.get_type().get_type_symbol());

    Symbol_name rhs(rhs_tree, csym->get_scope(), false);
    Symbol* p = rhs.lookup_for_use(true).untag;
    if (!p)
        compile_error("unknown name `" + rhs.get_name() + "'");

    /* Make sure that the final scope we looked in actually is a
       class. This is to wield out stuff like
         int i; struct a {} the_a; int j = the_a.::i; */
    Class_scope* look_scope = dynamic_cast<Class_scope*>(rhs.get_scope());
    if (!look_scope)
        compile_error("invalid qualified name on the RHS of `.' or `->'");
    Class_symbol* look_class = look_scope->get_class_symbol();
    if (look_class != csym) {
        /* up-cast the expression, so that user code knows which
           base we access */
        if (!look_class->is_unique_base_class_of(csym))
            compile_error("`" + look_class->get_name() + "' is not a unique base class of `" + csym->get_name() + "'");
        lhs = Expr_result(make_derived_to_base_cast(lhs.get_tree(),
                                                    look_class->get_type().with_qualifiers(lhs.get_type())),
                          lhs.get_kind());
    }

    if (Function_symbol* fsym = dynamic_cast<Function_symbol*>(p)) {
        /* Function call */
        Annotated<LeafName>* name = make_name(fsym->get_name(), Type(), fsym);
        if (rhs.is_qualified())
            name->add_flag(Annotation::af_DirectCall);
        return Expr_result(lhs.get_tree(), name, fsym);
    } else if (Variable_symbol* vsym = dynamic_cast<Variable_symbol*>(p)) {
        /* Variable access */
        if (vsym->is_member_variable()) {
            /* Member variable:
                 [vsym, TYPE] DotMember
                   expr
                   .
                   [vsym, TYPE] variable name
               In addition, if object is const and variable is not mutable,
               type is const. */
            if (vsym->get_class() != look_class && !vsym->get_class()->is_unique_base_class_of(look_class))
                compile_error("attempt to access member variable of `" + vsym->get_class()->get_name()
                              + "' which is not a unique base class of `" + look_class->get_name() + "'");
            Type vt = vsym->get_type();
            if (lhs.get_type().is_qualified(Type::q_Const) && (vsym->get_storage_class() != s_Mutable))
                vt.add_qualifier(Type::q_Const);
            return Expr_result(new Annotated<PtreeDotMemberExpr>(vt, vsym,
                                                                 lhs.get_tree(),
                                                                 Ptree::List(make_static_leaf("."),
                                                                             make_name(vsym))),
                               lhs.get_kind());
        } else {
            /* Static variable:
                 [no symbol, TYPE] CommaExpr
                   expr
                   ,
                   [vsym, TYPE] variable name
               Rationale: caller can assume that all DotMember
               actually access the object */
            compile_warning("using a static variable with object", rhs_tree);
            return Expr_result(make_comma_expr(lhs.get_tree(), make_name(vsym)), lhs.get_kind());
        }
    } else {
        compile_error("name `" + p->get_name() + "' not allowed at RHS of `.' or `->'");
    }
}

/** "dot-member" access, "obj.member". */
PUBLIC Expr_result
Expr_annotator::visit_dotmember(PtreeDotMemberExpr* e)
{
    expect_ptree(e->Second(), '.');

    Expr_result lhs = visit(e->First());
    if (!lhs.get_type().is_class_type())
        compile_error("left-hand side of `.' is not of class type");

    return process_member_access(lhs, e->Third());
}

/** "arrow-member" access, "ptr->member". We must resolve the operator ->
    if the lhs is not a pointer. */
PUBLIC Expr_result
Expr_annotator::visit_arrowmember(PtreeArrowMemberExpr* e)
{
    expect_ptree(e->Second(), "->");

    Expr_result lhs = visit(e->First());

    int loop_count = 0;
    while (lhs.get_type().is_class_type()) {
        /* prevent endless loops */
        if (++loop_count > PTR_DELEGATION_LIMIT) {
            compile_warning("Whatever you drank, it didn't contribute to your health:", e);
            compile_error("Pointer delegation takes too long to resolve, bailing out.");
        }

        Class_symbol* csym = downcast<Class_symbol*>(lhs.get_type().get_type_symbol());
        Class_scope* cscope = csym->get_scope();

        /* Try operator -> */
        Function_symbol* fsym = dynamic_cast<Function_symbol*>(cscope->lookup_here(Symbol_name::PTR_OPERATOR_NAME, false).untag);
        if (fsym) {
            Overload_resolver resolver(true);
            resolver.add_arg(lhs);
            resolver.add_function(fsym, true);

            bool is_ambig;
            Overload_candidate* cand = resolver.get_best(&is_ambig);
            if (is_ambig)
                compile_error("operator -> is ambiguous");
            if (cand) {
                /* it is not an error if there is no candidate */
                lhs.set_value(make_unary_funcall(make_name(cand->fsig),
                                                 cand->fsig->get_return_type(),
                                                 resolver.get_arg(0).get_tree()),
                              cand->fsig->get_return_type());
                continue;
            }
        }

        /* Try conversion to pointer */
        Overload_resolver resolver(true);
        resolver.add_arg(lhs);
        resolver.add_builtin_unary_ops(unary_delete_or_arrow_predicate);

        bool is_ambig;
        Overload_candidate* cand = resolver.get_best(&is_ambig);
        if (is_ambig)
            compile_error("conversion to pointer for -> is ambiguous");
        if (!cand)
            compile_error("no possible conversion to pointer for operator ->");

        lhs = resolver.get_arg(0);
    }

    if (!lhs.get_type().get_kind() == Type::k_Pointer
        || !lhs.get_type().get_basis_type().is_class_type())
        compile_error("left-hand-side of operator -> must be pointer to class type");

    return process_member_access(Expr_result(make_prefix_expr(lhs.get_type().get_basis_type(),
                                                              make_static_leaf("*"),
                                                              lhs.get_tree()),
                                             Expr_result::k_LValue),
                                 e->Third());
}

/** Pointer-to-member expression "lhs .* rhs". */
PRIVATE Expr_result
Expr_annotator::process_pm_expr(Expr_result lhs, const Expr_result& rhs)
{
    if (!lhs.get_type().is_class_type())
        compile_error("left side of `.*' must be class");
    if (rhs.get_type().get_kind() != Type::k_Member)
        compile_error("right side of `.*' must be member pointer");

    Type ltype = lhs.get_type();
    Type rtype = rhs.get_type().get_class_type().with_qualifiers(rhs.get_type().get_member_type());
    Class_symbol* lclass = downcast<Class_symbol*>(ltype.get_type_symbol());
    Class_symbol* rclass = downcast<Class_symbol*>(rtype.get_type_symbol());

    if (rclass != lclass) {
        /* we must allow "(derived).*(pm-base)" */
        if (!rclass->is_unique_base_class_of(lclass))
            compile_error("cannot use a pointer-to-member-of-" + rclass->get_name()
                          + " with an object of type " + lclass->get_name());
        lhs = Expr_result(make_derived_to_base_cast(lhs.get_tree(), rtype),
                          lhs.get_kind());
    }

    /* distinguish function and object */
    Type memtype = rhs.get_type().get_member_type();
    if (memtype.get_kind() == Type::k_Function) {
        /* function. Return a bound member function */
        /* refuse calling a non-const member function on a const-object */
        if (ltype.is_more_qualified_than(rtype))
            compile_error("class is more qualified than member pointer");
        return Expr_result(lhs.get_tree(),
                           rhs.get_tree(),
                           memtype);
    } else {
        /* object. Return an object */
        return Expr_result(new Annotated<PtreePmExpr>(memtype.with_qualifiers(ltype),
                                                      0,
                                                      lhs.get_tree(),
                                                      Ptree::List(make_static_leaf(".*"),
                                                                  rhs.get_tree())),
                           lhs.get_kind());
    }
}

/** Pointer-to-member expression. Syntax is [lhs .* rhs] or [lhs ->* rhs] */
PUBLIC Expr_result
Expr_annotator::visit_pm (PtreePmExpr* e)
{
    if (e->Second()->Eq("->*")) {
        // FIXME: operator overloading
        Expr_result lhs = visit(e->First());
        if (lhs.get_type().get_kind() != Type::k_Pointer && !lhs.get_type().get_basis_type().is_object_type())
            compile_error("operator ->* needs a pointer on the LHS");
        return process_pm_expr(Expr_result(make_prefix_expr(lhs.get_type().get_basis_type(),
                                                            make_static_leaf("*"),
                                                            lhs.get_tree()),
                                           Expr_result::k_LValue),
                               visit(e->Third()));
    } else if (e->Second()->Eq(".*")) {
        return process_pm_expr(visit(e->First()),
                               visit(e->Third()));
    } else
        bogus_ptree_error("expected .* or ->*", e);
}

/**************************** Ternary Operator ***************************/

/** Make ternary operator expression. */
static Annotated<PtreeCondExpr>*
make_cond_expr(Type ty, Ptree* i, Ptree* t, Ptree* e)
{
    return new Annotated<PtreeCondExpr>(ty, 0, i,
                                        Ptree::List(make_static_leaf("?"),
                                                    t,
                                                    make_static_leaf(":"),
                                                    e));
}

static Implicit_conversion*
generate_ics_for_ternary(Expr_result e1, Expr_result e2)
{
    /* if e2 is an lvalue, e1 can be converted to match e2 if e1
       can be implicitly converted to "reference to T2" if the
       reference binds directly (i.e. no temporary). */
    if (e2.is_lvalue()) {
        Implicit_conversion* ics = generate_implicit_conversion(e1,
                                                                e2.get_type().make_reference_type(),
                                                                0,
                                                                true /* with user-def */,
                                                                false /* no copy-init */,
                                                                false /* is IOA */);
        if (!ics->uses_temporary())
            return ics;
    }

    e1.convert_to_rvalue();
    e2.convert_to_rvalue();

    /* otherwise, attempt to convert e1 to e2 */
    return generate_implicit_conversion(e1, e2.get_type(), 0, true, false, false);
}

/** Visit ternary expression [if ? then : else] */
PUBLIC Expr_result
Expr_annotator::visit_cond(PtreeCondExpr* p)
{
    expect_ptree(p->Second(), '?');
    expect_ptree(p->Nth(3), ':');

    Expr_result i = visit(p->First()); // if
    Expr_result t = visit(p->Third()); // then
    Expr_result e = visit(p->Nth(4));  // else

    Implicit_conversion* ics = generate_implicit_conversion(i, bool_type, 0,
                                                            true, true, false);
    if (!ics)
        compile_error("unable to convert first arg of ?: to bool");
    i = ics->make_tree(i);

    if (t.get_type().is_void() || e.get_type().is_void()) {
        /* 5.16p2: if either type is cv-void, do standard conversions.
           If one is "throw", type is type of other; otherwise is void.
           In particular, it always is a rvalue. */
        t.do_std_conversions();
        e.do_std_conversions();
        Type ty = (dynamic_cast<PtreeThrowExpr*>(t.get_tree())
                   ? e.get_type()
                   : dynamic_cast<PtreeThrowExpr*>(e.get_tree())
                   ? t.get_type()
                   : void_type);
        return Expr_result(make_cond_expr(ty, i.get_tree(),
                                          t.get_tree(), e.get_tree()),
                           Expr_result::k_RValue);
    }

    if (!t.get_type().is_same_unqualified_type(e.get_type())
        && (t.get_type().is_class_type() || e.get_type().is_class_type()))
    {
        /* 5.16p3: different type, one is class type. Attempt to
           convert t to e, or e to t. */
        Implicit_conversion* ics_cvt_t = generate_ics_for_ternary(t, e);
        Implicit_conversion* ics_cvt_e = generate_ics_for_ternary(e, t);
        if (ics_cvt_e && ics_cvt_t)
            compile_error("ternary operator application is ambiguous");
        if (ics_cvt_t)
            t = ics_cvt_t->make_tree(t);
        if (ics_cvt_e)
            e = ics_cvt_e->make_tree(e);
    }

    if (t.is_lvalue() && e.is_lvalue() && t.get_type().is_same_unqualified_type(e.get_type())) {
        return Expr_result(make_cond_expr(t.get_type().with_qualifiers(e.get_type()),
                                          i.get_tree(), t.get_tree(), e.get_tree()),
                           Expr_result::k_LValue);
    }

    // FIXME: do overload resolution if both are class types

    t.do_std_conversions();
    e.do_std_conversions();
    bool two_npc = t.is_npc() && e.is_npc();
    if (t.get_type().is_same_unqualified_type(e.get_type()))
        ;
    else if ((t.get_type().is_arithmetic_type() || t.get_type().is_enum_type())
             && (e.get_type().is_arithmetic_type() || e.get_type().is_enum_type()))
        do_usual_conversions(&t, &e);
    else if (!two_npc
             && (t.get_type().get_kind() == Type::k_Pointer || t.is_npc())
             && (e.get_type().get_kind() == Type::k_Pointer || e.is_npc()))
    {
        /* pointer/pointer or pointer/npc */
        do_pointer_arith_conversions(&t, &e);
    } else if (!two_npc
               && (t.get_type().get_kind() == Type::k_Member || t.is_npc())
               && (e.get_type().get_kind() == Type::k_Member || e.is_npc()))
    {
        /* member/member or member/npc */
        do_mptr_arith_conversions(&t, &e);
    } else {
        compile_error("invalid arguments to ternary operator");
    }

    assert(t.get_type().is_same_unqualified_type(e.get_type()));

    return Expr_result(make_cond_expr(t.get_type().with_qualifiers(e.get_type()),
                                      i.get_tree(), t.get_tree(), e.get_tree()),
                       Expr_result::k_RValue);
}

/************************ Function Call and Casts ************************/
/**************************** Helper functions ***************************/

// bool
// convert_expr_to_bool(Expr_result* res)
// {
//     Implicit_conversion* ics = generate_implicit_conversion(*res, bool_type, 0,
//                                                             true, false, false);
//     if (!ics)
//         return false;

//     *res = ics->make_tree(*res);
//     return true;
// }

// bool
// convert_expr_to_integral(Expr_result* res)
// {
//     if (res->get_type().is_class_type()) {
//         Overload_resolver resolver;
//         resolver.add_arg(*res);
//         resolver.add_builtin_unary_ops(cast_to_enum_predicate);
//         if (!resolver.get_best(0))
//             return false;
//         *res = resolver.get_arg(0);
//         return true;
//     }
//     if (res->get_type().is_int() || res->get_type().is_enum_type())
//         return true;
//     return false;
// }

/** Given the type tree in a cxx_cast<T>, return the type T. */
PRIVATE Type
Expr_annotator::get_cast_type(Ptree* type_args)
{
    /* the type of a cast is:
       [< [[type-specifier declarator]] >] */
    expect_ptree(type_args->First(), '<');
    expect_ptree(type_args->Third(), '>');

    Ptree* inside = type_args->Second();
    if (inside->IsLeaf() || inside->Length() != 1 || inside->First()->IsLeaf() || inside->First()->Length() != 2)
        compile_error("syntax error in C++ cast");

    Type t = parse_type(inside->First()->First(), current_scope, 0, false);
    if (!parse_abstract_declarator(inside->First()->Second(), current_scope, &t))
        compile_error("bogus declarator in C++ cast");
    return t;
}

/** Given the expression list in a cxx_cast<T>(x), return the expression x. */
PRIVATE Expr_result
Expr_annotator::get_cast_expr(Ptree* tree)
{
    if (tree->IsLeaf() || tree->Length() != 1)
        compile_error("C++ cast expects exactly one argument");
    return visit(tree->First());
}

/** Attempt to static_cast /res/ to target, return true iff successful. */
PRIVATE bool
Expr_annotator::try_static_cast(Type target, bool enforce_const, Expr_result* res)
{
    /* anything can be cast to void */
    if (target.is_void()) {
        res->convert_to(void_type);
        return true;
    }

    /* void can't be cast anywhere */
    if (res->get_type().is_void())
        return false;

    /* forward ICS */
    if (Implicit_conversion* ics = generate_implicit_conversion(*res, target, 0,
                                                                true, false, false))
    {
        *res = ics->make_tree(*res);
        return true;
    }

    /* untyped values can't be cast anywhere */
    if (!res->is_value())
        return false;

    /* additional conversions: integral -> enum */
    if (target.is_enum_type() && (res->get_type().is_int() || res->get_type().is_enum_type())) {
        res->convert_to(target);
        return true;
    }

    /* B* -> D*, void* -> anything* */
    if (target.get_kind() == Type::k_Pointer && res->get_type().get_kind() == Type::k_Pointer) {
        Type hbase = res->get_type().get_basis_type();
        Type wbase = target.get_basis_type();
        if (enforce_const && hbase.is_more_qualified_than(wbase))
            return false;
        if (hbase.get_kind() == Type::k_Function || wbase.get_kind() == Type::k_Function)
            return false;
        if (hbase.is_void() || wbase.is_void()
            || (hbase.is_class_type() && wbase.is_class_type()
                && downcast<Class_symbol*>(hbase.get_type_symbol())->is_unique_base_class_of(dynamic_cast<Class_symbol*>(wbase.get_type_symbol()))))
        {
            res->convert_to(target);
            return true;
        }
    }

    /* D::* -> B::* */
    if (target.get_kind() == Type::k_Member && res->get_type().get_kind() == Type::k_Member) {
        Type hclass = res->get_type().get_class_type();
        Type wclass = target.get_class_type();
        if (enforce_const && hclass.is_more_qualified_than(wclass))
            return false;
        if (res->get_type().get_member_type().is_same_unqualified_type(target.get_member_type())
            && downcast<Class_symbol*>(wclass.get_type_symbol())->is_unique_base_class_of(downcast<Class_symbol*>(hclass.get_type_symbol())))
        {
            res->convert_to(target);
            return true;
        }
    }

    return false;
}

/** Attempt to do reinterpret_cast. */
bool
try_reinterpret_cast(Type t, bool enforce_const, Expr_result* res)
{
    Type ht = res->get_type();
    if (!ht.is_valid())
        return false;

    if (t.get_kind() == Type::k_Pointer) {
        /* int -> pointer */
        if (ht.is_int() || ht.is_enum_type()) {
            res->convert_to(t);
            return true;
        }

        if (t.get_basis_type().get_kind() == Type::k_Function) {
            /* pointer-to-function/function can be cast to pointer-to-function */
            if (ht.get_kind() == Type::k_Function ||
                (ht.get_kind() == Type::k_Pointer &&
                 ht.get_basis_type().get_kind() == Type::k_Function))
            {
                res->convert_to_pointer();
                res->convert_to(t);
                return true;
            }
        } else {
            if (ht.get_kind() == Type::k_Array ||
                (ht.get_kind() == Type::k_Pointer &&
                 ht.get_basis_type().get_kind() != Type::k_Function))
            {
                // FIXME: shall not cast away constness
                res->convert_to_fpointer();
                res->convert_to(t);
                return true;
            }
        }
    } else if (t.get_kind() == Type::k_Reference) {
        /* an object can be cast to a reference */
        if (!res->is_lvalue())
            return false;
        if (enforce_const && ht.is_more_qualified_than(t.get_basis_type()))
            return false;
        res->convert_to(t);
        return true;
    } else if (t.is_int() && ht.get_kind() == Type::k_Pointer) {
        /* pointer -> int */
        res->convert_to(t);
        return true;
    } else if (t.get_kind() == Type::k_Member && ht.get_kind() == Type::k_Member) {
        /* member -> member */
        if (enforce_const && ht.get_class_type().is_more_qualified_than(t.get_class_type()))
            return false;
        if ((ht.get_member_type().get_kind() == Type::k_Function)
            + (t.get_member_type().get_kind() == Type::k_Function) == 1)
            return false;
        res->convert_to(t);
        return true;
    }
    return false;
}

/************************ These generate the trees ***********************/

PRIVATE Expr_result
Expr_annotator::do_dynamic_cast(Ptree* type_args, Ptree* cast_args)
{
    Type t = get_cast_type(type_args);
    Expr_result arg = get_cast_expr(cast_args);
    compile_error("dynamic_cast geht noch nicht");
}

PRIVATE Expr_result
Expr_annotator::do_reinterpret_cast(Ptree* type_args, Ptree* cast_args)
{
    Type t = get_cast_type(type_args);
    Expr_result arg = get_cast_expr(cast_args);
    if (!try_reinterpret_cast(t, true, &arg))
        compile_error("invalid reinterpret_cast");
    return arg;
}

PRIVATE Expr_result
Expr_annotator::do_static_cast(Ptree* type_args, Ptree* cast_args)
{
    Type t = get_cast_type(type_args);
    Expr_result arg = get_cast_expr(cast_args);
    if (!try_static_cast(t, true, &arg))
        compile_error("invalid static_cast");
    return arg;
}

PRIVATE Expr_result
Expr_annotator::do_const_cast(Ptree* type_args, Ptree* cast_args)
{
    Type t = get_cast_type(type_args);
    Expr_result arg = get_cast_expr(cast_args);
    compile_error("const_cast geht noch nicht");
}

/** Do C-style cast.
    \param t target type
    \param arg parameter expression */
PRIVATE Expr_result
Expr_annotator::do_ccast(Type t, Ptree* arg)
{
    Expr_result res = visit(arg);
    if (try_static_cast(t, false, &res) || try_reinterpret_cast(t, false, &res))
        return res;
    else
        compile_error("can't do this type conversion");
}

/** Make function call.
    \param target  target type
    \param arglist list of arguments [a , b , c] */
PUBLIC Expr_result
Expr_annotator::do_fstyle_cast(Type target, Ptree* arglist)
{
    if (arglist && arglist->Length() == 1) {
        /* If the expression list is a single expression, [...]
           equivalent to the corresponding cast expression (5.4).
           => that is, it is identical to a C-style cast(!) */
        return do_ccast(target, arglist->Car());
    } else {
        Expr_result res;
        res.set_value(Init_handler(current_scope, 0, false).make_constructor_call(target, arglist), target);
        return res;
    }
}

PUBLIC void
Expr_annotator::add_parms_from_arglist(Overload_resolver* resolver, Ptree* p)
{
    /* list is either null or [ex , ex , ...] */
    if (!p)
        return;

    while (p) {
        resolver->add_arg(visit(p->Car()));
        p = p->Cdr();
        if (!p)
            break;
        expect_ptree(p->Car(), ',');
        p = p->Cdr();
    }
}

/** Make function call.
    \param lhs  left-hand side of the function call, i.e. the function
                to call
    \param arglist list of arguments [a , b , c] */
PRIVATE Expr_result
Expr_annotator::do_funcall (Expr_result lhs, Ptree* arglist)
{
    if (lhs.is_value()) {
        /* call to object which has a defined type. This includes
           non-overloaded functions. */
        if (lhs.get_type().is_class_type()) {
            /* Call to object of class type, 13.3.1.1.2 */
            Class_symbol* csym = downcast<Class_symbol*>(lhs.get_type().get_type_symbol());

            Overload_resolver resolver(true);
            resolver.add_arg(lhs);
            add_parms_from_arglist(&resolver, arglist);

            if (Function_symbol* fsym = dynamic_cast<Function_symbol*>(csym->get_scope()->lookup_here(Symbol_name::CALL_OPERATOR_NAME, false).untag))
                resolver.add_function(fsym, true);

            /* attempt conversions to function pointer */
            {
                Conversion_op_map op_map;
                enumerate_conversion_ops(lhs, &op_map);
                for (Conversion_op_map::iterator i = op_map.begin(); i != op_map.end(); ++i) {
                    Type cvt_target = i->first->get_return_type().sans_reference();
                    if (cvt_target.get_kind() == Type::k_Pointer)
                        cvt_target = cvt_target.get_basis_type();
                    if (cvt_target.get_kind() == Type::k_Function) {
                        /* okay, we can call it through a surrogate function.
                           cvt_target now is "RT (A1, A2, A3)" but we need
                           "RT (FPTR, A1, A2, A3)". */
                        resolver.add_signature(Function_signature::make_builtin(cvt_target.with_first_arg(cvt_target.make_pointer_type())));
                    }
                }
            }

            bool is_ambig;
            Overload_candidate* best = resolver.get_best(&is_ambig);
            if (is_ambig)
                compile_error("call to object is ambiguous");
            if (!best)
                compile_error("no matching function call operator");

            if (best->fsig->is_builtin()) {
                /* call through surrogate function. Overload_resolver will have converted
                   the object to a function pointer. */
                assert(resolver.get_arg(0).get_type().get_kind() == Type::k_Pointer);
                assert(resolver.get_arg(0).get_type().get_basis_type().get_kind() == Type::k_Function);

                Annotated_funcall_maker afm(resolver.get_arg(0).get_tree(),
                                            best->fsig->get_return_type());
                for (unsigned i = 1; i < resolver.get_arg_count(); ++i)
                    afm.add_arg(resolver.get_arg(i).get_tree());

                Expr_result ex;
                ex.set_value(afm.make_funcall(), best->fsig->get_return_type());
                return ex;
            } else {
                /* call to "operator()" method */
                Annotated_funcall_maker afm(make_name(best->fsig),
                                            best->fsig->get_return_type());
                for (unsigned i = 0; i < resolver.get_arg_count(); ++i)
                    afm.add_arg(resolver.get_arg(i).get_tree());

                Expr_result ex;
                ex.set_value(afm.make_funcall(), best->fsig->get_return_type());
                return ex;
            }
        }

        /* at this point, lhs must be [pointer to] function */
        Type ftype = lhs.get_type();
        if (ftype.get_kind() == Type::k_Pointer)
            ftype = ftype.get_basis_type();
        if (ftype.get_kind() != Type::k_Function)
            compile_error("cannot call object of type `" + lhs.get_type().get_human_readable_type() + "'");

        Overload_resolver resolver(false);
        add_parms_from_arglist(&resolver, arglist);
        Function_signature tmp_fsig(ftype, Type(), ftype, s_Static, 0, 0);
        resolver.add_signature(&tmp_fsig);

        /* check whether it's possible */
        if (!resolver.get_best(0))
            compile_error("invalid argument list for call to function pointer");

        /* call it */
        Annotated_funcall_maker afm(lhs.get_tree(), ftype.get_return_type());
        for (unsigned i = 0; i < resolver.get_arg_count(); ++i)
            afm.add_arg(resolver.get_arg(i).get_tree());

        Expr_result ex;
        ex.set_value(afm.make_funcall(), ftype.get_return_type());
        return ex;
    } else if (lhs.is_bound_pmf()) {
        /* call to bound member function, as in
              int i = (obj.*pmf)(1);
           The structure we're getting is
           + type = type of the member function (i.e. "int (*)(int)")
           + tree = member function expression (i.e. "pmf" of type
             "int (a::*)(int)")
           + obj_tree = object expression (i.e. "obj" of type "a") */
        Overload_resolver resolver(false);
        Annotation* oanno = downcast<Annotation*>(lhs.get_object());

        resolver.set_object(Expr_result(lhs.get_object(),
                                        oanno->get_type(),
                                        Expr_result::k_RValue));
        add_parms_from_arglist(&resolver, arglist);

        Function_signature tmp_fsig(lhs.get_type(), oanno->get_type(),
                                    lhs.get_type(), s_Member, 0, 0);
        resolver.add_signature(&tmp_fsig);

        /* check whether it's possible */
        if (!resolver.get_best(0))
            compile_error("invalid parameter list for call to bound member function");

        /* make final call */
        Annotated_funcall_maker afm(lhs.get_tree(), lhs.get_type().get_return_type());
        for (unsigned i = 0; i < resolver.get_arg_count(); ++i)
            afm.add_arg(resolver.get_arg(i).get_tree());

        Expr_result ex;
        ex.set_value(afm.make_funcall(), lhs.get_type().get_return_type());
        return ex;
    } else if (lhs.is_function() || lhs.is_bound_member()) {
        bool invented_this_ptr = false;
        Overload_resolver resolver(false);
        if (lhs.is_bound_member()) {
            /* call to bound member function, as in "obj.func()" */
            Annotation* oanno = downcast<Annotation*>(lhs.get_object());
            resolver.set_object(Expr_result(lhs.get_object(),
                                            oanno->get_type(),
                                            Expr_result::k_RValue));
        } else {
            /* normal function, as in "func()". Might be member call with
               implicit "this" parameter. */
            Type t = current_scope->get_this_type();
            if (t.is_valid()) {
                resolver.set_object(Expr_result(make_this_star(t), Expr_result::k_LValue));
                invented_this_ptr = true;
            }
        }
        add_parms_from_arglist(&resolver, arglist);
        assert(lhs.get_function());
        resolver.add_function(lhs.get_function(), true);

        bool is_ambig;
        Overload_candidate* best = resolver.get_best(&is_ambig);
        if (is_ambig)
            compile_error("call to `" + lhs.get_function()->get_name() + "' is ambiguous");
        if (!best)
            compile_error("no matching function for call to `" + lhs.get_function()->get_name() + "'");

        /* Now, make the function call */
        fill_in_overload_annotation(lhs.get_tree(), best->fsig, best->fsig->get_call_type());
        Annotated_funcall_maker afm(lhs.get_tree(), best->fsig->get_return_type());
        if (best->fsig->get_storage_specifier() == s_Member) {
            assert(resolver.is_object());
            for (unsigned i = 0; i < resolver.get_arg_count(); ++i)
                afm.add_arg(resolver.get_arg(i).get_tree());

            Expr_result ex;
            ex.set_value(afm.make_funcall(), best->fsig->get_return_type());
            return ex;
        } else if (resolver.is_object()) {
            for (unsigned i = 1; i < resolver.get_arg_count(); ++i)
                afm.add_arg(resolver.get_arg(i).get_tree());

            Expr_result ex;
            if (invented_this_ptr) {
                /* we have invented the "this" argument; so it isn't
                   actually part of the semantics. Drop it again. */
                ex.set_value(afm.make_funcall(), best->fsig->get_return_type());
            } else {
                compile_warning("calling a static function with object", arglist);
                ex.set_value(make_comma_expr(resolver.get_arg(0).get_tree(),
                                             afm.make_funcall()),
                             best->fsig->get_return_type());
            }
            return ex;
        } else {
            for (unsigned i = 0; i < resolver.get_arg_count(); ++i)
                afm.add_arg(resolver.get_arg(i).get_tree());

            Expr_result ex;
            ex.set_value(afm.make_funcall(), best->fsig->get_return_type());
            return ex;
        }
    } else
        assert(0);
}

/** Function-style cast. This one's identical to calling a constructor. */
PUBLIC Expr_result
Expr_annotator::visit_fstylecastexpr (PtreeFstyleCastExpr* e)
{
    /* [type ( arglist )] */
    expect_ptree(e->Second(), '(');
    expect_ptree(e->Nth(3), ')');
    return do_fstyle_cast(parse_type(e->First(), current_scope, 0, false),
                          e->Third());
}

/** Visit function call expression. */
PUBLIC Expr_result
Expr_annotator::visit_funcall (PtreeFuncallExpr* e)
{
    /* foo()       => [Name:foo ( null )]
       ::foo()     => [Name:[:: foo] ( null )]
       o.foo()     => [DotMember:[Name:o . Name:foo] ( null )]
       o.a::foo()  => [DotMember:[Name:o . Name:[a :: foo]] ( null )]
       p->foo()    => [ArrowMember:[p -> foo] ( null )] */

    /* The LHS of a function call can be:
       - a type name
       - an object of type "function" or "pointer to function"
       - a bound member function
       - an object that overloads "operator ()"
       - an object that is convertible to a function pointer */

    expect_ptree(e->Second(), '(');
    expect_ptree(e->Nth(3), ')');
    Ptree* arglist = e->Third();

    if (ptree_is_name(e->First())) {
        /* special cases */
        if (!e->First()->IsLeaf()) {
            Ptree* first_name = e->First()->First();
            if (first_name->Eq("dynamic_cast"))
                return do_dynamic_cast(e->First()->Second(), arglist);
            if (first_name->Eq("reinterpret_cast"))
                return do_reinterpret_cast(e->First()->Second(), arglist);
            if (first_name->Eq("const_cast"))
                return do_const_cast(e->First()->Second(), arglist);
            if (first_name->Eq("static_cast"))
                return do_static_cast(e->First()->Second(), arglist);
        }

        /* normal cases */
        Symbol_name sname(e->First(), current_scope, false);
        Symbol* sym = sname.lookup_for_use(false).untag;

        if (!sym) {
            compile_error("unknown symbol `" + std::string(e->First()->ToString()) + "' in function call");
        } else if (Typedef_symbol* tdsym = dynamic_cast<Typedef_symbol*>(sym)) {
            return do_fstyle_cast(tdsym->get_type(), arglist);
        } else if (Type_symbol* tysym = dynamic_cast<Type_symbol*>(sym)) {
            return do_fstyle_cast(tysym->get_type(), arglist);
        } else if (Function_symbol* fsym = dynamic_cast<Function_symbol*>(sym)) {
            // FIXME: do Koenig lookup etc.
            return do_funcall(visit(e->First()), arglist);
        } else {
            return do_funcall(visit(e->First()), arglist);
        }
    } else
        return do_funcall(visit(e->First()), arglist);
}

/** Visit C-style cast expression. */
PUBLIC Expr_result
Expr_annotator::visit_cast(PtreeCastExpr* p)
{
    expect_ptree(p->First(), '(');
    expect_ptree(p->Third(), ')');

    Ptree* typ = p->Second();
    Ptree* arg = p->Nth(3);
    Type t;

    try {
        t = parse_type(typ->First(), current_scope, 0, false);
        if (!parse_abstract_declarator(typ->Second(), current_scope, &t))
            compile_error("you'll never see this");
    }
    catch(...) {
        if (dynamic_cast<PtreeParenExpr*>(arg)) {
            /* (function) (args) */
            return do_funcall(visit(convert_decl_to_expr(typ->First(),
                                                         typ->Second())),
                              convert_comma_expr_to_list(arg->Second()));
        } else if (dynamic_cast<PtreeUnaryExpr*>(arg)) {
            /* (expr) + expr */
            Ptree* oper = arg->First();
            if (oper->Eq('&') || oper->Eq('+') || oper->Eq('-') || oper->Eq('*')) {
                compile_warning("expression of style `(expr) " +
                                std::string(oper->ToString()) +
                                " expr' might be translated wrong", oper);
                return visit_infix(new PtreeInfixExpr(convert_decl_to_expr(typ->First(),
                                                                           typ->Second()),
                                                      arg));
            }
        }
        compile_error("invalid C-style cast");
    }

    return do_ccast(t, arg);
}

/* Visit brace. This simplifies initializer handling. */
PUBLIC Expr_result
Expr_annotator::visit_brace(PtreeBrace* b)
{
    compile_error("brace expression not valid here");
}

/******************************* Assignment ******************************/

/** Predicate for *= and /=. These accept "cv-arith&" on the LHS,
    and "arith" or "enum" on the RHS. */
Type
binary_multeq_predicate(Type l, Type r)
{
    if (l.get_kind() != Type::k_Reference)
        return Type();

    r = r.sans_reference();
    if (l.get_basis_type().is_arithmetic_type()) {
        if (r.is_int() || r.is_enum_type())
            return make_binary_function_type(l, r.get_promoted_integer(), l);
        else if (r.is_same_unqualified_type(float_type))
            return make_binary_function_type(l, double_type, l);
        else if (r.is_float())
            return make_binary_function_type(l, r, l);
    }
    return Type();
}

/** Predicate for += and -=. These accept "cv-arith&" on the LHS,
    and "arith" or "enum" on the RHS; or "cv-obj*&" on the LHS and
    ptrdiff_t on the RHS. */
Type
binary_addeq_predicate(Type l, Type r)
{
    if (l.get_kind() != Type::k_Reference)
        return Type();

    r = r.sans_reference();
    if (l.get_basis_type().is_arithmetic_type()) {
        if (r.is_int() || r.is_enum_type())
            return make_binary_function_type(l, r.get_promoted_integer(), l);
    } else if (l.get_basis_type().get_kind() == Type::k_Pointer
               && l.get_basis_type().get_basis_type().is_object_type()) {
        /* caller will sort out functions where r is not convertible to
           ptrdiff_t */
        return make_binary_function_type(l, ptrdiff_type, l);
    }
    return Type();
}

/** Predicate for %=, <<=, etc. These accept "cv-integral&" on the LHS,
    and "arith" or "enum" on the RHS. */
Type
binary_inteq_predicate(Type l, Type r)
{
    // FIXME: I'm unsure about the "is_int" here. Objects which
    // convert to fp types should probably take part in overload
    // resolution, although they'll violate constraints on the builtin
    // operator should this function be chosen. Formally, an argument
    // of fp type can be passed to a function "operator%=(VQ L&, R)"
    // with R being a promoted integral type. gcc seems not to include
    // them in the result set.
    r = r.sans_reference();
    if (l.get_kind() == Type::k_Reference && l.get_basis_type().is_int()
        && (r.is_int() || r.is_enum_type()))
        return make_binary_function_type(l, r.get_promoted_integer(), l);
    else
        return Type();
}

/** Visit assignment or compound assignment expression. */
PUBLIC Expr_result
Expr_annotator::visit_assign(PtreeAssignExpr* p)
{
    Expr_result lhs = visit(p->First());
    Expr_result rhs = visit(p->Third());

    if (p->Second()->Eq('=')) {
        /* operator=:
           - if lhs is class type, look up matching lhs::operator=.
             Assignment fails if it doesn't exist. The built-in operator
             is synthesized in Class_symbol::finish_definition(); if it
             doesn't exist, this means we can't synthesize one
             (constraint violation). We look directly into the class and
             don't use the normal lookup rules; this way, we won't
             accidentially find a base class assignment operator.
           - otherwise, it is builtin assignment operator (no way to
             define such an operator); convert right operand accordingly */

        if (lhs.get_type().is_class_type()) {
            Class_symbol* csym = downcast<Class_symbol*>(lhs.get_type().get_type_symbol());
            Function_symbol* fsym = dynamic_cast<Function_symbol*>(csym->lookup_helper(Symbol_name::ASSIGNMENT_OPERATOR_NAME).untag);
            if (!fsym)
                compile_error("unable to assign to an object of type `" + csym->get_name() + "'");

            Overload_resolver resolver(false);
            resolver.set_object(lhs);
            resolver.add_arg(rhs);
            resolver.add_function(fsym, true);

            bool is_ambig;
            Overload_candidate* cand = resolver.get_best(&is_ambig);
            if (is_ambig)
                compile_error("assignment to `" + csym->get_name() + "' is ambiguous");
            if (!cand)
                compile_error("no matching `operator=' in assignment to `" + csym->get_name() + "'");

            Annotated_funcall_maker afm(make_name(cand->fsig),
                                        cand->fsig->get_return_type());
            afm.add_arg(resolver.get_arg(0).get_tree());
            afm.add_arg(resolver.get_arg(1).get_tree());

            Expr_result res;
            res.set_value(afm.make_funcall(), cand->fsig->get_return_type());
            return res;
        }

        /* not a class type - must be builtin operator. */
        if (!lhs.is_modifyable_lvalue() || !lhs.is_value() || lhs.get_type().is_void())
            compile_error("LHS of assignment is not modifyable lvalue");

        Implicit_conversion* ics = generate_implicit_conversion(rhs,
                                                                lhs.get_type(),
                                                                0,
                                                                true /* with user-def */,
                                                                true /* is copy-init */,
                                                                false /* is IOA */);
        if (!ics)
            compile_error("unable to convert `" + rhs.get_type().get_human_readable_type()
                          + "' into `" + lhs.get_type().get_human_readable_type() + "'");

        return Expr_result(new Annotated<PtreeAssignExpr>(lhs.get_type(),
                                                          0,
                                                          lhs.get_tree(),
                                                          Ptree::List(p->Second(),
                                                                      ics->make_tree(rhs).get_tree())),
                           Expr_result::k_LValue);
    }


    /* operator@=: we have to look up any "operator@=(LHS,RHS)"
       and "LHS::operator@=(RHS)".

       NOTE: according to CWG defect 221, the blurb about "assignment
       operator" does not apply to compound assignment operators. This
       is consistent with "++" et al, btw. */

    Ptree* oper_tree = p->Second();
    if (lhs.get_type().get_kind() == Type::k_Userdef || rhs.get_type().get_kind() == Type::k_Userdef) {
        /* operator name */
        const char* operator_name = Symbol_name::get_operator_name(oper_tree);

        /* do overload resolution */
        Overload_resolver resolver(true);
        resolver.add_arg(lhs);
        resolver.add_arg(rhs);

        /* class member candidates */
        Class_symbol* csym;
        if (lhs.get_type().get_kind() == Type::k_Userdef && (csym = dynamic_cast<Class_symbol*>(lhs.get_type().get_type_symbol()))) {
            Function_symbol* fsym = dynamic_cast<Function_symbol*>(csym->get_scope()->lookup_here(operator_name, false).untag);
            if (fsym)
                resolver.add_function(fsym, false);
        }

        /* global candidates */
        if (Function_symbol* fsym = dynamic_cast<Function_symbol*>(current_scope->lookup_unqualified(operator_name).untag))
            resolver.add_function(fsym, false);

        if (oper_tree->Eq("*=") || oper_tree->Eq("/="))
            resolver.add_builtin_binary_ops(binary_multeq_predicate);
        else if (oper_tree->Eq("+=") || oper_tree->Eq("-="))
            resolver.add_builtin_binary_ops(binary_addeq_predicate);
        else if (oper_tree->Eq("%=") || oper_tree->Eq("<<=") || oper_tree->Eq(">>=")
                 || oper_tree->Eq("&=") || oper_tree->Eq("^=") || oper_tree->Eq("|="))
            resolver.add_builtin_binary_ops(binary_inteq_predicate);
        else
            bogus_ptree_error("huh? strange operator", oper_tree);

        bool is_ambig;
        Overload_candidate* cand = resolver.get_best(&is_ambig);
        if (is_ambig)
            compile_error("call to operator `" + std::string(oper_tree->ToString()) + "' is ambiguous");
        if (cand) {
            if (!cand->fsig->is_builtin()) {
                /* user-defined operator */
                Annotated_funcall_maker afm(make_name(cand->fsig), cand->fsig->get_return_type());
                afm.add_arg(resolver.get_arg(0).get_tree());
                afm.add_arg(resolver.get_arg(1).get_tree());

                Expr_result res;
                res.set_value(afm.make_funcall(), cand->fsig->get_return_type());
                return res;
            }

            lhs = resolver.get_arg(0);
            rhs = resolver.get_arg(1);
        }
    }

    /* when we're here, it's a builtin operator */
    if (!lhs.is_modifyable_lvalue())
        compile_error("need modifyable lvalue on the lhs of a compound assignment");
    if (!lhs.is_value() || !rhs.is_value())
        compile_error("invalid operand to compound assignment");

    if (oper_tree->Eq("*=") || oper_tree->Eq("/=")) {
        /* arithmetic types */
        if (rhs.get_type().is_enum_type())
            rhs.convert_to(rhs.get_type().get_promoted_integer());
        if (lhs.get_type().is_arithmetic_type() && rhs.get_type().is_arithmetic_type())
            return Expr_result(new Annotated<PtreeAssignExpr>(lhs.get_type(), 0,
                                                              lhs.get_tree(),
                                                              Ptree::List(oper_tree,
                                                                          rhs.get_tree())),
                               Expr_result::k_LValue);
        compile_error("invalid operand to *= or /=");
    } else if (oper_tree->Eq("+=") || oper_tree->Eq("-=")) {
        /* arithmetic, or pointer type */
        if (lhs.get_type().get_kind() == Type::k_Pointer) {
            check_ptr_arith(lhs.get_type());
            if (rhs.get_type().is_int() || rhs.get_type().is_enum_type())
                rhs.convert_to(ptrdiff_type);
            else
                compile_error("need integer on rhs of pointer += / -=");
        } else if (lhs.get_type().is_arithmetic_type()) {
            if (rhs.get_type().is_arithmetic_type())
                /* okay */;
            else if (rhs.get_type().is_enum_type())
                rhs.convert_to(rhs.get_type().get_promoted_integer());
            else
                compile_error("invalid operand to += or -=");
        } else
            compile_error("invalid left operand to += or -=");
        return Expr_result(new Annotated<PtreeAssignExpr>(lhs.get_type(), 0,
                                                          lhs.get_tree(),
                                                          Ptree::List(oper_tree,
                                                                      rhs.get_tree())),
                           Expr_result::k_LValue);
    } else if (oper_tree->Eq("%=") || oper_tree->Eq("<<=") || oper_tree->Eq(">>=")
               || oper_tree->Eq("&=") || oper_tree->Eq("^=") || oper_tree->Eq("|="))
    {
        /* integer type */
        if (!lhs.get_type().is_int())
            compile_error(std::string(oper_tree->ToString()) + " needs integer on the lhs");
        if (rhs.get_type().is_enum_type())
            rhs.convert_to(rhs.get_type().get_promoted_integer());
        else if (rhs.get_type().is_int())
            /* ok */;
        else
            compile_error(std::string(oper_tree->ToString()) + " needs integer or enum on the rhs");
        return Expr_result(new Annotated<PtreeAssignExpr>(lhs.get_type(), 0,
                                                          lhs.get_tree(),
                                                          Ptree::List(oper_tree,
                                                                      rhs.get_tree())),
                           Expr_result::k_LValue);
    } else
        bogus_ptree_error("strange operator", oper_tree);
}

/***************************** Array Indexing ****************************/

/** Predicate for [] operator. This one takes a pointer or array and
    an arithmetic type. */
static Type
index_predicate(Type l, Type r)
{
    l = l.sans_reference();
    r = r.sans_reference();
    if (l.get_kind() == Type::k_Pointer || l.get_kind() == Type::k_Array) {
        if (r.is_arithmetic_type() || r.is_enum_type())
            return make_binary_function_type(l.get_basis_type().make_pointer_type(),
                                             ptrdiff_type,
                                             void_type /* return type is egal */);
    } else if (r.get_kind() == Type::k_Pointer || r.get_kind() == Type::k_Array) {
        if (l.is_arithmetic_type() || l.is_enum_type())
            return make_binary_function_type(ptrdiff_type,
                                             l.get_basis_type().make_pointer_type(),
                                             void_type /* return type is egal */);
    }
    return Type();
}

PUBLIC Expr_result
Expr_annotator::visit_array(PtreeArrayExpr* p)
{
    expect_ptree(p->Second(), '[');
    expect_ptree(p->Nth(3), ']');

    Expr_result lhs = visit(p->First());
    Expr_result rhs = visit(p->Third());

    if (lhs.get_type().get_kind() == Type::k_Userdef || rhs.get_type().get_kind() == Type::k_Userdef) {
        Overload_resolver resolver(true);
        resolver.add_arg(lhs);
        resolver.add_arg(rhs);

        /* class member candidates */
        Class_symbol* csym;
        if (lhs.get_type().get_kind() == Type::k_Userdef && (csym = dynamic_cast<Class_symbol*>(lhs.get_type().get_type_symbol()))) {
            Function_symbol* fsym = dynamic_cast<Function_symbol*>(csym->get_scope()->lookup_here(Symbol_name::INDEX_OPERATOR_NAME, false).untag);
            if (fsym)
                resolver.add_function(fsym, false);
        }

        /* global candidates */
        if (Function_symbol* fsym = dynamic_cast<Function_symbol*>(current_scope->lookup_unqualified(Symbol_name::INDEX_OPERATOR_NAME).untag))
            resolver.add_function(fsym, false);

        resolver.add_builtin_binary_ops(index_predicate);

        bool is_ambig;
        Overload_candidate* cand = resolver.get_best(&is_ambig);
        if (is_ambig)
            compile_error("call to operator[] is ambiguous");
        if (cand) {
            if (!cand->fsig->is_builtin()) {
                Annotated_funcall_maker afm(make_name(cand->fsig),
                                            cand->fsig->get_return_type());
                afm.add_arg(resolver.get_arg(0).get_tree());
                afm.add_arg(resolver.get_arg(1).get_tree());

                Expr_result res;
                res.set_value(afm.make_funcall(), cand->fsig->get_return_type());
                return res;
            }

            lhs = resolver.get_arg(0);
            rhs = resolver.get_arg(1);
        }
    }

    /* built-in operator */
    lhs.do_std_conversions();
    rhs.do_std_conversions();

    if (lhs.get_type().get_kind() == Type::k_Pointer) {
        check_ptr_arith(lhs.get_type());
        if (rhs.get_type().is_int() || rhs.get_type().is_enum_type())
            rhs.convert_to(ptrdiff_type);
        else
            compile_error("invalid type `" + rhs.get_type().get_human_readable_type() + "' for array subscript");

        return Expr_result(new Annotated<PtreeArrayExpr>(lhs.get_type().get_basis_type(), 0,
                                                         lhs.get_tree(),
                                                         Ptree::List(p->Second(),
                                                                     rhs.get_tree(),
                                                                     p->Nth(3))),
                           Expr_result::k_LValue);
    } else if (rhs.get_type().get_kind() == Type::k_Pointer) {
        check_ptr_arith(rhs.get_type());
        if (lhs.get_type().is_int() || lhs.get_type().is_enum_type())
            lhs.convert_to(ptrdiff_type);
        else
            compile_error("invalid type `" + lhs.get_type().get_human_readable_type() + "' for array subscript");

        compile_warning("swapping sides of array subscript expression", p);
        return Expr_result(new Annotated<PtreeArrayExpr>(rhs.get_type().get_basis_type(), 0,
                                                         rhs.get_tree(),
                                                         Ptree::List(p->Second(),
                                                                     lhs.get_tree(),
                                                                     p->Nth(3))),
                           Expr_result::k_LValue);
    }
    compile_error("invalid types for array subscript");
}