summaryrefslogtreecommitdiff
path: root/Build/source/utils/asymptote/application.cc
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/utils/asymptote/application.cc')
-rw-r--r--Build/source/utils/asymptote/application.cc713
1 files changed, 713 insertions, 0 deletions
diff --git a/Build/source/utils/asymptote/application.cc b/Build/source/utils/asymptote/application.cc
new file mode 100644
index 00000000000..0a3c0f10353
--- /dev/null
+++ b/Build/source/utils/asymptote/application.cc
@@ -0,0 +1,713 @@
+/*****
+ * 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