/*****
* application.cc
* Andy Hammerlindl 2005/05/20
*
* An application is a matching of arguments in a call expression to formal
* parameters of a function.  Since the language allows default arguments,
* keyword arguments, rest arguments, and anything else we think of, this
* is not a simple mapping.
*****/

#include "application.h"
#include "exp.h"
#include "coenv.h"
#include "runtime.h"
#include "runarray.h"

using namespace types;
using absyntax::varinit;
using absyntax::arrayinit;
using absyntax::arglist;

namespace trans {

// Lower scores are better.  Packed is added onto the other qualifiers so
// we may score both exact and casted packed arguments.
const score FAIL=0, EXACT=1, CAST=2;
const score PACKED=2;

bool castable(env &e, formal& target, formal& source) {
 return target.Explicit ? equivalent(target.t,source.t)
   : e.castable(target.t,source.t, symbol::castsym);
}

score castScore(env &e, formal& target, formal& source) {
 return equivalent(target.t,source.t) ? EXACT :
   (!target.Explicit &&
    e.fastCastable(target.t,source.t)) ? CAST : FAIL;
}


void restArg::transMaker(coenv &e, Int size, bool rest) {
 // Push the number of cells and call the array maker.
 e.c.encode(inst::intpush, size);
 e.c.encode(inst::builtin, rest ? run::newAppendedArray :
            run::newInitializedArray);
}

void restArg::trans(coenv &e, temp_vector &temps)
{
 // Push the values on the stack.
 for (mem::list<arg *>::iterator p = inits.begin(); p != inits.end(); ++p)
   (*p)->trans(e, temps);

 if (rest)
   rest->trans(e, temps);

 transMaker(e, (Int)inits.size(), (bool)rest);
}

class maximizer {
 app_list l;

 // Tests if x is as good (or better) an application as y.
 bool asgood(application *x, application *y) {
   // Matches to open signatures are always worse than matches to normal
   // signatures.
   if (x->sig->isOpen)
     return y->sig->isOpen;
   else if (y->sig->isOpen)
     return true;

   assert (x->scores.size() == y->scores.size());

   // Test if each score in x is no higher than the corresponding score in
   // y.
   return std::equal(x->scores.begin(), x->scores.end(), y->scores.begin(),
                     std::less_equal<score>());
 }

 bool better(application *x, application *y) {
   return asgood(x,y) && !asgood(y,x);
 }

 // Add an application that has already been determined to be maximal.
 // Remove any other applications that are now not maximal because of its
 // addition.
 void addMaximal(application *x) {
   app_list::iterator y=l.begin();
   while (y!=l.end())
     if (better(x,*y))
       y=l.erase(y);
     else
       ++y;
   l.push_front(x);
 }

 // Tests if x is maximal.
 bool maximal(application *x) {
   for (app_list::iterator y=l.begin(); y!=l.end(); ++y)
     if (better(*y,x))
       return false;
   return true;
 }

public:
 maximizer() {}

 void add(application *x) {
   if (maximal(x))
     addMaximal(x);
 }

 app_list result() {
   return l;
 }
};

ty *restCellType(signature *sig) {
 formal& f=sig->getRest();
 if (f.t) {
   array *a=dynamic_cast<array *>(f.t);
   if (a)
     return a->celltype;
 }

 return 0;
}

void application::initRest() {
 formal& f=sig->getRest();
 if (f.t) {
   ty *ct = restCellType(sig);
   if (!ct)
     vm::error("formal rest argument must be an array");

   rf=formal(ct, symbol::nullsym, false, f.Explicit);
 }
 if (f.t || sig->isOpen) {
   rest=new restArg();
 }
}

//const Int REST=-1;
const Int NOMATCH=-2;

Int application::find(symbol name) {
 formal_vector &f=sig->formals;
 for (size_t i=index; i<f.size(); ++i)
   if (f[i].name==name && args[i]==0)
     return (Int)i;
 return NOMATCH;
}

bool application::matchDefault() {
 if (index==args.size())
   return false;
 else {
   formal &target=getTarget();
   if (target.defval) {
     args[index]=new defaultArg(target.t);
     advanceIndex();
     return true;
   }
   else
     return false;
 }
}

bool application::matchArgumentToRest(env &e, formal &source,
                                     varinit *a, size_t evalIndex)
{
 if (rest) {
   score s=castScore(e, rf, source);
   if (s!=FAIL) {
     rest->add(seq.addArg(a, rf.t, evalIndex));
     scores.push_back(s+PACKED);
     return true;
   }
 }
 return false;
}

bool application::matchAtSpot(size_t spot, env &e, formal &source,
                             varinit *a, size_t evalIndex)
{
 formal &target=sig->getFormal(spot);
 if(target.t->kind == types::ty_error) return false;

 score s=castScore(e, target, source);

 if (s == FAIL)
   return false;
 else if (sig->formalIsKeywordOnly(spot) && source.name == symbol::nullsym)
   return false;
 else {
   // The argument matches.
   args[spot]=seq.addArg(a, target.t, evalIndex);
   if (spot==index)
     advanceIndex();
   scores.push_back(s);
   return true;
 }
}

bool application::matchArgument(env &e, formal &source,
                               varinit *a, size_t evalIndex)
{
 assert(!source.name);

 if (index==args.size())
   // Try to pack into the rest array.
   return matchArgumentToRest(e, source, a, evalIndex);
 else
   // Match here, or failing that use a default and try to match at the next
   // spot.
   return matchAtSpot(index, e, source, a, evalIndex) ||
     (matchDefault() && matchArgument(e, source, a, evalIndex));
}

bool application::matchNamedArgument(env &e, formal &source,
                                    varinit *a, size_t evalIndex)
{
 assert(source.name);

 Int spot=find(source.name);
 return spot!=NOMATCH && matchAtSpot(spot, e, source, a, evalIndex);
}

bool application::complete() {
 if (index==args.size())
   return true;
 else if (matchDefault())
   return complete();
 else
   return false;
}

bool application::matchRest(env &e, formal &source, varinit *a,
                           size_t evalIndex) {
 // First make sure all non-rest arguments are matched (matching to defaults
 // if necessary).
 if (complete())
   // Match rest to rest.
   if (rest) {
     formal &target=sig->getRest();
     score s=castScore(e, target, source);
     if (s!=FAIL) {
       rest->addRest(seq.addArg(a, target.t, evalIndex));
       scores.push_back(s);
       return true;
     }
   }
 return false;
}

// When the argument should be evaluated, possibly adjusting for a rest
// argument which occurs before named arguments.
size_t adjustIndex(size_t i, size_t ri)
{
 return i < ri ? i : i+1;
}

bool application::matchSignature(env &e, types::signature *source,
                                arglist &al) {
 formal_vector &f=source->formals;

#if 0
 cout << "num args: " << f.size() << endl;
 cout << "num keyword-only: " << sig->numKeywordOnly << endl;
#endif

 size_t ri = al.rest.val ? al.restPosition : f.size();

 // First, match all of the named (non-rest) arguments.
 for (size_t i=0; i<f.size(); ++i)
   if (f[i].name)
     if (!matchNamedArgument(e, f[i], al[i].val, adjustIndex(i,ri)))
       return false;

 // Then, the unnamed.
 for (size_t i=0; i<f.size(); ++i)
   if (!f[i].name)
     if (!matchArgument(e, f[i], al[i].val, adjustIndex(i,ri)))
       return false;

 // Then, the rest argument.
 if (source->hasRest())
   if (!matchRest(e, source->getRest(), al.rest.val, ri))
     return false;

 // Fill in any remaining arguments with their defaults.
 return complete();
}

bool application::matchOpen(env &e, signature *source, arglist &al) {
 assert(rest);

 // Pack all given parameters into the rest argument.
 formal_vector &f=source->formals;
 for (size_t i = 0; i < f.size(); ++i)
   if (al[i].name)
     // Named arguments are not handled by open signatures.
     return false;
   else
     rest->add(seq.addArg(al[i].val, f[i].t, i));

 if (source->hasRest())
   rest->addRest(new varinitArg(al.rest.val, source->getRest().t));

 return true;
}

application *application::match(env &e, function *t, signature *source,
                               arglist &al) {
 assert(t->kind==ty_function);
 application *app=new application(t);

 bool success = t->getSignature()->isOpen ?
   app->matchOpen(e, source, al) :
   app->matchSignature(e, source, al);

 //cout << "MATCH " << success << endl;

 return success ? app : 0;
}

void application::transArgs(coenv &e) {
 temp_vector temps;

 for(arg_vector::iterator a=args.begin(); a != args.end(); ++a)
   (*a)->trans(e,temps);

 if (rest)
   rest->trans(e,temps);
}

bool application::exact() {
 if (sig->isOpen)
   return false;
 for (score_vector::iterator p = scores.begin(); p != scores.end(); ++p)
   if (*p != EXACT)
     return false;
 return true;
}

bool application::halfExact() {
 if (sig->isOpen)
   return false;
 if (scores.size() != 2)
   return false;
 if (scores[0] == EXACT && scores[1] == CAST)
   return true;
 if (scores[0] == CAST && scores[1] == EXACT)
   return true;
 return false;
}

// True if any of the formals have names.
bool namedFormals(signature *sig)
{
 formal_vector& formals = sig->formals;
 size_t n = formals.size();
 for (size_t i = 0; i < n; ++i) {
   if (formals[i].name)
     return true;
 }
 return false;
}

// Tests if arguments in the source signature can be matched to the formals
// in the target signature with no casting or packing.
// This allows overloaded args, but not named args.
bool exactMightMatch(signature *target, signature *source)
{
 // Open signatures never exactly match.
 if (target->isOpen)
   return false;

#if 0
 assert(!namedFormals(source));
#endif

 formal_vector& formals = target->formals;
 formal_vector& args = source->formals;

 // Sizes of the two lists.
 size_t fn = formals.size(), an = args.size();

 // Indices for the two lists.
 size_t fi = 0, ai = 0;

 while (fi < fn && ai < an) {
   if (equivalent(formals[fi].t, args[ai].t)) {
     // Arguments match, move to the next.
     ++fi; ++ai;
   } else if (formals[fi].defval) {
     // Match formal to default value.
     ++fi;
   } else {
     // Failed to match formal.
     return false;
   }
 }

 assert(fi == fn || ai == an);

 // Packing array arguments into the rest formal is inexact.  Do not allow it
 // here.
 if (ai < an)
   return false;

 assert(ai == an);

 // Match any remaining formal to defaults.
 while (fi < fn)
   if (formals[fi].defval) {
     // Match formal to default value.
     ++fi;
   } else {
     // Failed to match formal.
     return false;
   }

 // Non-rest arguments have matched.
 assert(fi == fn && ai == an);

 // Try to match the rest argument if given.
 if (source->hasRest()) {
   if (!target->hasRest())
     return false;

   if (!equivalent(source->getRest().t, target->getRest().t))
     return false;
 }

 // All arguments have matched.
 return true;
}

// Tries to match applications without casting.  If an application matches
// here, we need not attempt to match others with the slower, more general
// techniques.
app_list exactMultimatch(env &e,
                        types::overloaded *o,
                        types::signature *source,
                        arglist &al)
{
 assert(source);

 app_list l;

 // This can't handle named arguments.
 if (namedFormals(source))
   return l; /* empty */

 for (ty_vector::iterator t=o->sub.begin(); t!=o->sub.end(); ++t)
   {
     if ((*t)->kind != ty_function)
       continue;

     function *ft = (function *)*t;

     // First we run a test to see if all arguments could be exactly matched.
     // If this returns false, no such match is possible.
     // If it returns true, an exact match may or may not be possible.
     if (!exactMightMatch(ft->getSignature(), source))
       continue;

     application *a=application::match(e, ft, source, al);

     // Consider calling
     //   void f(A a=new A, int y)
     // with
     //   f(3)
     // This matches exactly if there is no implicit cast from int to A.
     // Otherwise, it does not match.
     // Thus, there is no way to know if the
     // match truly is exact without looking at the environment.
     // In such a case, exactMightMatch() must return true, but there is no
     // exact match.  Such false positives are eliminated here.
     //
     // Consider calling
     //   void f(int x, real y=0.0, int z=0)
     // with
     //   f(1,2)
     // exactMightMatch() will return true, matching 1 to x and 2 to z, but the
     // application::match will give an inexact match of 1 to x to 2 to y, due
     // to the cast from int to real.  Therefore, we must test for exactness
     // even after matching.
     if (a && a->exact())
       l.push_back(a);
   }

 //cout << "EXACTMATCH " << (!l.empty()) << endl;
 return l;
}

bool halfExactMightMatch(env &e,
                        signature *target, types::ty *t1, types::ty *t2)
{
 formal_vector& formals = target->formals;
 if (formals.size() < 2)
   return false;
 if (formals.size() > 2) {
   // We should probably abort the whole matching in this case.  For now,
   // return true and let the usual matching handle it.
   return true;
 }

 assert(formals[0].t);
 assert(formals[1].t);

 // These casting tests if successful will be repeated again by
 // application::match.  It would be nice to avoid this somehow, but the
 // additional complexity is probably not worth the minor speed improvement.
 if (equivalent(formals[0].t, t1))
   return e.fastCastable(formals[1].t, t2);
 else
   return equivalent(formals[1].t, t2) && e.fastCastable(formals[0].t, t1);
}

// Most common after exact matches are cases such as
//   2 + 3.4   (int, real) --> (real, real)
// that is, binary operations where one of the operands matches exactly and the
// other does not.  This function searches for these so-called "half-exact"
// matches.  This should only be called after exactMultimatch has failed.
app_list halfExactMultimatch(env &e,
                            types::overloaded *o,
                            types::signature *source,
                            arglist &al)
{
 assert(source);

 app_list l;


 // Half exact is only in the case of two arguments.
 formal_vector& formals = source->formals;
 if (formals.size() != 2 || source->hasRest())
   return l; /* empty */

 // This can't handle named arguments.
 if (namedFormals(source))
   return l; /* empty */

 // Alias the two argument types.
 types::ty *t1 = formals[0].t;
 types::ty *t2 = formals[1].t;

 assert(t1); assert(t2);

 for (ty_vector::iterator t=o->sub.begin(); t!=o->sub.end(); ++t)
   {
     if ((*t)->kind != ty_function)
       continue;

     function *ft = (function *)*t;

#if 1
     if (!halfExactMightMatch(e, ft->getSignature(), t1, t2))
       continue;
#endif

     application *a=application::match(e, ft, source, al);

#if 1
     if (a && a->halfExact())
       l.push_back(a);
#endif
   }

 return l;
}

// Simple check if there are too many arguments to match the candidate
// function.
// A "tooFewArgs" variant was also implemented at some point, but did
// not give any speed-up.
bool tooManyArgs(types::signature *target, types::signature *source) {
 return source->getNumFormals() > target->getNumFormals() &&
   !target->hasRest();
}

// The full overloading resolution system, which handles casting of arguments,
// packing into rest arguments, named arguments, etc.
app_list inexactMultimatch(env &e,
                          types::overloaded *o,
                          types::signature *source,
                          arglist &al)
{
 assert(source);

 app_list l;


#define DEBUG_GETAPP 0
#if DEBUG_GETAPP
 //cout << "source: " << *source << endl;
 //cout << "ARGS: " << source->getNumFormals() << endl;
 bool perfect=false;
 bool exact=false;
 bool halfExact=false;
#endif

 for(ty_vector::iterator t=o->sub.begin(); t!=o->sub.end(); ++t) {
   if ((*t)->kind==ty_function) {
#if DEBUG_GETAPP
     function *ft = dynamic_cast<function *>(*t);
     signature *target = ft->getSignature();
     if (equivalent(target, source))
       perfect = true;
#endif

     // Check if there are two many arguments to match.
     if (tooManyArgs((*t)->getSignature(), source))
       continue;

     application *a=application::match(e, (function *)(*t), source, al);
     if (a)
       l.push_back(a);

#if DEBUG_GETAPP
     if (a && !namedFormals(source)) {
       assert(a->exact() == exactlyMatchable(ft->getSignature(), source));
       if (a->halfExact() && !namedFormals(source)) {
         assert(halfExactMightMatch(e, target, source->getFormal(0).t,
                                    source->getFormal(1).t));
       }

     }
     if (a && a->exact())
       exact = true;
     if (a && a->halfExact())
       halfExact = true;
#endif
   }
 }

#if DEBUG_GETAPP
 cout << (perfect     ? "PERFECT" :
          exact       ? "EXACT" :
          halfExact   ? "HALFEXACT" :
          "IMPERFECT")
      << endl;
#endif

 if (l.size() > 1) {
   // Return the most specific candidates.
   maximizer m;
   for (app_list::iterator x=l.begin(); x!=l.end(); ++x) {
     assert(*x);
     m.add(*x);
   }
   return m.result();
 }
 else
   return l;
}

enum testExactType {
 TEST_EXACT,
 DONT_TEST_EXACT,
};

// Sanity check for multimatch optimizations.
void sameApplications(app_list a, app_list b, testExactType te) {
 assert(a.size() == b.size());

 if (te == TEST_EXACT) {
   for (app_list::iterator i = a.begin(); i != a.end(); ++i) {
     if (!(*i)->exact()) {
       cout << *(*i)->getType() << endl;
     }
     assert((*i)->exact());
   }
   for (app_list::iterator i = b.begin(); i != b.end(); ++i)
     assert((*i)->exact());
 }

 if (a.size() == 1)
   assert(equivalent(a.front()->getType(), b.front()->getType()));
}

app_list multimatch(env &e,
                   types::overloaded *o,
                   types::signature *source,
                   arglist &al)
{
 app_list a = exactMultimatch(e, o, source, al);
 if (!a.empty()) {
#if DEBUG_CACHE
   // Make sure that exactMultimatch and the fallback return the same
   // application(s).
   sameApplications(a, inexactMultimatch(e, o, source, al), TEST_EXACT);
#endif

   return a;
 }

 a = halfExactMultimatch(e, o, source, al);
 if (!a.empty()) {
#if DEBUG_CACHE
   sameApplications(a, inexactMultimatch(e, o, source, al), DONT_TEST_EXACT);
#endif

   return a;
 }

 // Slow but most general method.
 return inexactMultimatch(e, o, source, al);
}

} // namespace trans

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.