/**
  *  \file overload_resolver.cpp
  */

INTERFACE:

#include <vector>
#include <iosfwd>

#include "expr_result.h"
#include "garbage.h"

class Implicit_conversion;
class Function_signature;
class Function_symbol;
class Overload_resolver;

struct Overload_candidate : public virtual G_cleanup {
    Function_signature*                fsig;
    std::vector<Implicit_conversion*>  args;
};    

class Overload_resolver {
 public:
    typedef Overload_candidate Candidate;
 private:
    std::vector<Candidate*> candidates;

    bool                      have_object;
    bool                      is_operator;
    /* parameters. If there is an implicit object argument, it
       is first in this list. */
    std::vector<Expr_result>  args;

    friend class Overload_candidate;
};

IMPLEMENTATION:

#include <iostream>
#include "function.h"
#include "implicit_conversion.h"
#include "except.h"
#include "symbol_name.h"

/*************************** Overload_resolver ***************************/

PUBLIC
Overload_resolver::Overload_resolver(bool is_operator)
    : have_object(0), is_operator(is_operator)
{ }

PUBLIC void
Overload_resolver::add_arg(const Expr_result& res)
{
    args.push_back(res);
}

PUBLIC void
Overload_resolver::set_object(const Expr_result& res)
{
    assert(!have_object);
    assert(args.empty());
    assert(!is_operator);
    args.push_back(res);
    have_object  = true;
}

PUBLIC inline bool
Overload_resolver::is_object() const
{
    return have_object;    
}

/** Add signature to candidate set, if it is viable. 
    as_operator = true => if it is a member function, transform it into a function call
    (XX.operator(YY) => operator(XX, YY) */
PUBLIC void 
Overload_resolver::add_signature(Function_signature* sig)
{
    add_signature_with_type(sig, sig->get_proto_type());
}

PUBLIC void
Overload_resolver::add_signature_with_type(Function_signature* sig, Type t)
{
    /* first, analyze the function parameter count. */
    int nargs = t.get_num_function_args();
    bool is_ellipsis = nargs && t.get_function_arg(nargs-1).get_kind() == Type::k_Ellipsis;
    if (is_ellipsis)
        --nargs;

    Candidate* cand = new Candidate(sig);
    if (is_operator) {
        /* FIXME? reject operators with ellipsis args. They are not
           allowed; g++ doesn't even allow to define them (13.5). */
        if (is_ellipsis)
            return;

        /* A::operator@(B) => [A, B]
           operator@(A, B) => [A, B] */
        if (sig->get_storage_specifier() == s_Member) {
            if (nargs != args.size() - 1)
                return;
            if (Implicit_conversion* ics = generate_implicit_conversion(args[0],
                                                                        sig->get_this_type().make_reference_type(),
                                                                        0,
                                                                        false, /* no user-defined */
                                                                        true, /* is copy initialisation */
                                                                        true /* impl. obj. arg */))
                cand->args.push_back(ics);
            else
                return;
        } else {
            if (nargs != args.size())
                return;
        }
        int argindex = 0;
        for (unsigned i = cand->args.size(); i < args.size(); ++i) {
            Implicit_conversion* ics = generate_implicit_conversion(args[i], t.get_function_arg(argindex++), 
                                                                    0,
                                                                    true,
                                                                    true,
                                                                    false /* not impl. obj. arg */);
            if (ics)
                cand->args.push_back(ics);
            else
                return;
        }
    } else {
        /* Not an operator. 
           Member function:  A::foo(X,Y,Z) => [A, X, Y, Z]
                        or                       [X, Y, Z]
           Non-member function: foo(X,Y,Z) => [0, X, Y, Z]
                        or                       [X, Y, Z] */
        if (have_object) {
            if (sig->get_storage_specifier() == s_Member) {
                Implicit_conversion* ics = generate_implicit_conversion(args[0],
                                                                        sig->get_this_type().make_reference_type(),
                                                                        0, false, true, true);
                if (ics)
                    cand->args.push_back(ics);
                else
                    return;
            } else {
                cand->args.push_back(0);
            }
        }

        int need_args = args.size() - cand->args.size();
        if (nargs > need_args)
            return;
        if (nargs < need_args && !is_ellipsis)
            return;

        int argptr = 0;
        for (int i = cand->args.size(); i < args.size(); ++i) {
            Type argtype = t.get_function_arg(argptr);
            if (argtype.get_kind() == Type::k_Ellipsis) {
                /* ellipsis */
                if (!args[i].is_value())
                    return;
                Implicit_conversion* ics = new Implicit_conversion(args[i], 0);
                ics->add_conversion(Implicit_conversion::a_Ellipsis, argtype);
                cand->args.push_back(ics);
            } else {
                /* normal argument */
                ++argptr;
                if (Implicit_conversion* ics = generate_implicit_conversion(args[i],
                                                                            argtype,
                                                                            0,
                                                                            true,
                                                                            true,
                                                                            false)) 
                {
                    cand->args.push_back(ics);
                } else {
                    return;
                }
            }
        }
    }

    /* add the candidate */
    candidates.push_back(cand);
}

/** Add builtin "++" and "--" operators to the result set. 
    There are builtin ++ and -- operators for types "volatile T&" and "T&",
    where "T" is either an arithmetic type or pointer-to-object type */
PUBLIC void
Overload_resolver::add_builtin_incdec(bool is_increment)
{
    assert(!have_object && (args.size() == 1 || args.size() == 2));

    Conversion_op_map op_map;
    enumerate_conversion_ops(args[0], &op_map);

    for (Conversion_op_map::iterator i = op_map.begin(); i != op_map.end(); ++i) {
        Function_signature* sig = i->first;
        Type t = sig->get_proto_type().get_return_type();
        if (t.get_kind() != Type::k_Reference)
            continue;
        t = t.get_basis_type();

        /* operator-- doesn't apply to bool */
        if (t.is_same_unqualified_type(bool_type) && !is_increment)
            continue;

        /* can't be const */
        if (t.is_qualified(Type::q_Const))
            continue;

        /* arithmetic or pointer type */
        if (t.is_arithmetic_type() || (t.get_kind() == Type::k_Pointer && t.get_basis_type().is_object_type())) {
            Function_type_maker ftm;
            ftm.add_parameter(t.make_reference_type());
            if (args.size() == 2) {
                ftm.add_parameter(int_type);
                add_signature(Function_signature::make_builtin(ftm.make_function_type(t.get_unqualified_type())));
            } else {
                add_signature(Function_signature::make_builtin(ftm.make_function_type(t.make_reference_type())));
            }
        }
    }
}

/** Add built-in unary operators. Note that this one is only usable for operators
    which expect rvalues; it will never feed reference types into predicate.
    \param predicate a function which checks whether an argument of type t is a valid
           parameter for the operator. The predicate returns either Type() if the parameter
           is invalid, otherwise the signature of the operator (e.g. "bool->bool"). */
PUBLIC void
Overload_resolver::add_builtin_unary_ops(Type (*predicate)(Type t))
{
    assert(args.size() == 1);
    Conversion_op_map op_map;
    enumerate_conversion_ops(args[0], &op_map);
    for (Conversion_op_map::iterator i = op_map.begin(); i != op_map.end(); ++i) {
        Type ft = predicate(i->first->get_proto_type().get_return_type().sans_reference());
        if (ft.is_valid())
            add_signature(Function_signature::make_builtin(ft));
    }
}

/** Add built-in binary operators. Unloke add_builtin_unary_ops, this one
    will also feed reference types into the predicate (i.e. "int&" and "long"
    in a "+=" expression).
    \param predicate a function which checks whether there is a builtin operator
           which can take operands of types t1 and t2. If yes, returns the
           function type of the operator (i.e. "int&(int&,long)"), otherwise
           returns a null type ("Type()"). */
PUBLIC void
Overload_resolver::add_builtin_binary_ops(Type (*predicate)(Type t1, Type t2))
{
    assert(args.size() == 2);
    Conversion_op_map lhs_map, rhs_map;
    enumerate_conversion_ops(args[0], &lhs_map);
    enumerate_conversion_ops(args[1], &rhs_map);

    for (Conversion_op_map::iterator i = lhs_map.begin(); i != lhs_map.end(); ++i) {
        for (Conversion_op_map::iterator j = rhs_map.begin(); j != rhs_map.end(); ++j) {
            Type ft = predicate(i->first->get_return_type(), j->first->get_return_type());
            if (ft.is_valid())
                add_signature(Function_signature::make_builtin(ft));
        }
    }

    Type lhs_type = args[0].get_type();
    if (args[0].is_lvalue())
        lhs_type = lhs_type.make_reference_type();
    for (Conversion_op_map::iterator i = rhs_map.begin(); i != rhs_map.end(); ++i) {
        Type ft = predicate(lhs_type, i->first->get_return_type());
        if (ft.is_valid())
            add_signature(Function_signature::make_builtin(ft));
    }
    
    Type rhs_type = args[1].get_type();
    if (args[1].is_lvalue())
        rhs_type = rhs_type.make_reference_type();
    for (Conversion_op_map::iterator i = lhs_map.begin(); i != lhs_map.end(); ++i) {
        Type ft = predicate(i->first->get_return_type(), rhs_type);
        if (ft.is_valid())
            add_signature(Function_signature::make_builtin(ft));
    }
    
}

/** Add all signatures of a function to candidate set. If allow_dups
    is true, a function which already is in the set will be added
    again; this will cause an ambiguity should that function be
    chosen. If allow_dups is false, duplicates will not be added. If
    the Function_symbol itself contains dupes, those will make it into
    the set, though (this is a feature). */
PUBLIC void
Overload_resolver::add_function(Function_symbol* fsym, bool allow_dups)
{
    unsigned limit = candidates.size();
    for (Function_symbol::Sig_it i = fsym->sig_begin(); i != fsym->sig_end(); ++i)
        if (allow_dups || !have_signature(*i, limit))
            add_signature(*i);
}

PRIVATE bool
Overload_resolver::have_signature(Function_signature* fsig, unsigned limit)
{
    for (unsigned i = 0; i < limit; ++i)
        if (candidates[i]->fsig == fsig)
            return true;
    return false;
}

PUBLIC Overload_candidate*
Overload_resolver::get_best(bool* is_ambig)
{
    if (is_ambig)
        *is_ambig = false;

    if (candidates.empty())
        return 0;

    Candidate* best = candidates.front();
    for (unsigned i = 1; i < candidates.size(); ++i)
        if (candidates[i]->is_better_than(best))
            best = candidates[i];
    for (unsigned i = 0; i < candidates.size(); ++i) {
        if (best != candidates[i] && !best->is_better_than(candidates[i])) {
            /* ambiguous */
            if (is_ambig)
                *is_ambig = true;
            return 0;
        }
    }

    /* okay, it's not ambiguous. Check all ICSs. */
    best->fill_in_tree(this);
    return best;
}

PUBLIC inline unsigned
Overload_resolver::get_arg_count() const
{
    return args.size();
}

PUBLIC void
Overload_resolver::dump(std::ostream& os)
{
    os << "The candidate set contains " << candidates.size() << " signatures.\n";
    for (unsigned i = 0; i < candidates.size(); ++i) {
        Candidate* c = candidates[i];
        os << "- Candidate #" << (i+1) << ": " << c->fsig->get_proto_type().get_encoded_type() << ":\n";
        for (unsigned j = 0; j < c->args.size(); ++j) {
            os << "  + conversion for parameter " << (j+1) << ":\n";
            c->args[j]->dump(os);
        }
    }
}

PUBLIC inline Expr_result&
Overload_resolver::get_arg(int i)
{
    return args[i];
}

/********************** Overload_resolver::Candidate *********************/

PUBLIC
Overload_candidate::Overload_candidate(Function_signature* sig)
    : fsig(sig), args()
{ }

PUBLIC
Overload_candidate::~Overload_candidate()
{ }

/** Returns true iff candidate this is better than other. */
PUBLIC bool
Overload_candidate::is_better_than(Overload_candidate* other)
{
    assert(other->args.size() == args.size());

    /* a viable function F1 is better than another viable function
       F2 if for all arguments, ICSi(F1) is not a worse conversion
       sequence than ICSi(F2) ... */

    bool was_better = false;
    for (unsigned i = 0; i < args.size(); ++i) {
        if (!args[i] || !other->args[i]) {
            assert(i==0);
            continue;
        }
        if (other->args[i]->is_better_than(args[i], ICS_Types::c_CompareAll))
            return false;
        if (args[i]->is_better_than(other->args[i], ICS_Types::c_CompareAll))
            was_better = true;
    }

    /*  ... and then
        - for some argument j, ICSj(F1) is a better conversion
        sequence than ICSj(F2) ... */
    if (was_better)
        return true;

    /* FIXME: ... or, if not that
       - non-template is better than template
       - specialized template is better than general template
       - initialisation-by-user-defined-conversion rules here */
    return false;
}

PUBLIC void
Overload_candidate::fill_in_tree(Overload_resolver* resolver)
{
    /* We need an object if
       - we're doing a member call
       - the member is not a constructor */
    if (!resolver->have_object && !resolver->is_operator && fsig->get_storage_specifier() == s_Member)
        if (fsig->get_function()->get_function_kind() != Symbol_name::k_Constructor)
            compile_error("attempt to call member function without an object");

    for (unsigned i = 0; i < args.size(); ++i)
        if (args[i])
            resolver->args[i] = args[i]->make_tree(resolver->args[i]);
        else
            assert(i == 0 && resolver->have_object);
}