/***** * 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 && #ifdef FASTCAST e.fastCastable(target.t,source.t)) ? CAST : FAIL; #else e.castable(target.t,source.t, symbol::castsym)) ? CAST : FAIL; #endif } 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::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()); } 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(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; iadd(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); score s=castScore(e, target, source); if (s!=FAIL) { // The argument matches. args[spot]=seq.addArg(a, target.t, evalIndex); if (spot==index) advanceIndex(); scores.push_back(s); return true; } else return false; } 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) { // 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(new varinitArg(a, target.t)); scores.push_back(s); return true; } } return false; } bool application::matchSignature(env &e, types::signature *source, arglist &al) { formal_vector &f=source->formals; #if 0 cout << "num args: " << f.size() << endl; #endif // First, match all of the named (non-rest) arguments. for (size_t i=0; ihasRest()) if (!matchRest(e, source->getRest(), al.rest.val)) 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 exactlyMatchable(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; if (!exactlyMatchable(ft->getSignature(), source)) continue; application *a=application::match(e, ft, source, al); assert(a); // Consider calling // void f(int x, real y=0.0, int z=0) // with // f(1,2) // exactlyMatchable 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->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); #ifdef FASTCAST # define CASTABLE fastCastable #else # define CASTABLE castable #endif // These casting tests if successful will be repeating 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.CASTABLE(formals[1].t, t2); else return equivalent(formals[1].t, t2) && e.CASTABLE(formals[0].t, t1); #undef CASTABLE } // Most common after exact matches are cases such as // 2 + 3.4 // that is, binary operations were 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 two many arguments to match the candidate // function. 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(*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) { #ifdef EXACT_MATCH 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 // Make sure that exactMultimatch and the fallback return the same // application(s). sameApplications(a, inexactMultimatch(e, o, source, al), DONT_TEST_EXACT); #endif return a; } #endif // Slow but most general method. return inexactMultimatch(e, o, source, al); } } // namespace trans