"Fossies" - the Fresh Open Source Software Archive

Member "asymptote-2.61/application.cc" (18 Nov 2019, 18534 Bytes) of package /linux/misc/asymptote-2.61.src.tgz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "application.cc" see the Fossies "Dox" file reference documentation.

    1 /*****
    2  * application.cc
    3  * Andy Hammerlindl 2005/05/20
    4  *
    5  * An application is a matching of arguments in a call expression to formal
    6  * parameters of a function.  Since the language allows default arguments,
    7  * keyword arguments, rest arguments, and anything else we think of, this
    8  * is not a simple mapping.
    9  *****/
   10 
   11 #include "application.h"
   12 #include "exp.h"
   13 #include "coenv.h"
   14 #include "runtime.h"
   15 #include "runarray.h"
   16 
   17 using namespace types;
   18 using absyntax::varinit;
   19 using absyntax::arrayinit;
   20 using absyntax::arglist;
   21 
   22 namespace trans {
   23 
   24 // Lower scores are better.  Packed is added onto the other qualifiers so
   25 // we may score both exact and casted packed arguments.
   26 const score FAIL=0, EXACT=1, CAST=2;
   27 const score PACKED=2;
   28 
   29 bool castable(env &e, formal& target, formal& source) {
   30   return target.Explicit ? equivalent(target.t,source.t)
   31     : e.castable(target.t,source.t, symbol::castsym);
   32 }
   33 
   34 score castScore(env &e, formal& target, formal& source) {
   35   return equivalent(target.t,source.t) ? EXACT :
   36     (!target.Explicit &&
   37      e.fastCastable(target.t,source.t)) ? CAST : FAIL;
   38 }
   39 
   40 
   41 void restArg::transMaker(coenv &e, Int size, bool rest) {
   42   // Push the number of cells and call the array maker.
   43   e.c.encode(inst::intpush, size);
   44   e.c.encode(inst::builtin, rest ? run::newAppendedArray :
   45              run::newInitializedArray);
   46 }
   47 
   48 void restArg::trans(coenv &e, temp_vector &temps)
   49 {
   50   // Push the values on the stack.
   51   for (mem::list<arg *>::iterator p = inits.begin(); p != inits.end(); ++p)
   52     (*p)->trans(e, temps);
   53 
   54   if (rest)
   55     rest->trans(e, temps);
   56   
   57   transMaker(e, (Int)inits.size(), (bool)rest);
   58 }
   59 
   60 class maximizer {
   61   app_list l;
   62 
   63   // Tests if x is as good (or better) an application as y.
   64   bool asgood(application *x, application *y) {
   65     // Matches to open signatures are always worse than matches to normal
   66     // signatures.
   67     if (x->sig->isOpen)
   68       return y->sig->isOpen;
   69     else if (y->sig->isOpen)
   70       return true;
   71 
   72     assert (x->scores.size() == y->scores.size());
   73 
   74     // Test if each score in x is no higher than the corresponding score in
   75     // y.
   76     return std::equal(x->scores.begin(), x->scores.end(), y->scores.begin(),
   77                       std::less_equal<score>());
   78   }
   79 
   80   bool better(application *x, application *y) {
   81     return asgood(x,y) && !asgood(y,x);
   82   }
   83 
   84   // Add an application that has already been determined to be maximal.
   85   // Remove any other applications that are now not maximal because of its
   86   // addition.
   87   void addMaximal(application *x) {
   88     app_list::iterator y=l.begin();
   89     while (y!=l.end())
   90       if (better(x,*y))
   91         y=l.erase(y);
   92       else
   93         ++y;
   94     l.push_front(x);
   95   }
   96   
   97   // Tests if x is maximal.
   98   bool maximal(application *x) {
   99     for (app_list::iterator y=l.begin(); y!=l.end(); ++y)
  100       if (better(*y,x))
  101         return false;
  102     return true;
  103   }
  104 
  105 public:
  106   maximizer() {}
  107 
  108   void add(application *x) {
  109     if (maximal(x))
  110       addMaximal(x);
  111   }
  112 
  113   app_list result() {
  114     return l;
  115   }
  116 };
  117 
  118 ty *restCellType(signature *sig) {
  119   formal& f=sig->getRest();
  120   if (f.t) {
  121     array *a=dynamic_cast<array *>(f.t);
  122     if (a)
  123       return a->celltype;
  124   }
  125 
  126   return 0;
  127 }
  128 
  129 void application::initRest() {
  130   formal& f=sig->getRest();
  131   if (f.t) {
  132     ty *ct = restCellType(sig);
  133     if (!ct)
  134       vm::error("formal rest argument must be an array");
  135 
  136     rf=formal(ct, symbol::nullsym, false, f.Explicit);
  137   }
  138   if (f.t || sig->isOpen) {
  139     rest=new restArg();
  140   }
  141 }
  142 
  143 //const Int REST=-1; 
  144 const Int NOMATCH=-2;
  145 
  146 Int application::find(symbol name) {
  147   formal_vector &f=sig->formals;
  148   for (size_t i=index; i<f.size(); ++i)
  149     if (f[i].name==name && args[i]==0)
  150       return (Int)i;
  151   return NOMATCH;
  152 }
  153 
  154 bool application::matchDefault() {
  155   if (index==args.size())
  156     return false;
  157   else {
  158     formal &target=getTarget();
  159     if (target.defval) {
  160       args[index]=new defaultArg(target.t);
  161       advanceIndex();
  162       return true;
  163     }
  164     else
  165       return false;
  166   }
  167 }
  168 
  169 bool application::matchArgumentToRest(env &e, formal &source,
  170                                       varinit *a, size_t evalIndex)
  171 {
  172   if (rest) {
  173     score s=castScore(e, rf, source);
  174     if (s!=FAIL) {
  175       rest->add(seq.addArg(a, rf.t, evalIndex));
  176       scores.push_back(s+PACKED);
  177       return true;
  178     }
  179   }
  180   return false;
  181 }
  182 
  183 bool application::matchAtSpot(size_t spot, env &e, formal &source,
  184                               varinit *a, size_t evalIndex)
  185 {
  186   formal &target=sig->getFormal(spot);
  187   score s=castScore(e, target, source);
  188 
  189   if (s == FAIL)
  190     return false;
  191   else if (sig->formalIsKeywordOnly(spot) && source.name == symbol::nullsym)
  192     return false;
  193   else {
  194     // The argument matches.
  195     args[spot]=seq.addArg(a, target.t, evalIndex);
  196     if (spot==index)
  197       advanceIndex();
  198     scores.push_back(s);
  199     return true;
  200   }
  201 }
  202 
  203 bool application::matchArgument(env &e, formal &source,
  204                                 varinit *a, size_t evalIndex)
  205 {
  206   assert(!source.name);
  207 
  208   if (index==args.size())
  209     // Try to pack into the rest array.
  210     return matchArgumentToRest(e, source, a, evalIndex);
  211   else
  212     // Match here, or failing that use a default and try to match at the next
  213     // spot.
  214     return matchAtSpot(index, e, source, a, evalIndex) ||
  215       (matchDefault() && matchArgument(e, source, a, evalIndex));
  216 }
  217 
  218 bool application::matchNamedArgument(env &e, formal &source,
  219                                      varinit *a, size_t evalIndex)
  220 {
  221   assert(source.name);
  222 
  223   Int spot=find(source.name);
  224   return spot!=NOMATCH && matchAtSpot(spot, e, source, a, evalIndex);
  225 }
  226 
  227 bool application::complete() {
  228   if (index==args.size())
  229     return true;
  230   else if (matchDefault())
  231     return complete();
  232   else
  233     return false;
  234 }
  235 
  236 bool application::matchRest(env &e, formal &source, varinit *a,
  237                             size_t evalIndex) {
  238   // First make sure all non-rest arguments are matched (matching to defaults
  239   // if necessary).
  240   if (complete())
  241     // Match rest to rest.
  242     if (rest) {
  243       formal &target=sig->getRest();
  244       score s=castScore(e, target, source);
  245       if (s!=FAIL) {
  246         rest->addRest(seq.addArg(a, target.t, evalIndex));
  247         scores.push_back(s);
  248         return true;
  249       }
  250     }
  251   return false;
  252 }
  253   
  254 // When the argument should be evaluated, possibly adjusting for a rest
  255 // argument which occurs before named arguments.
  256 size_t adjustIndex(size_t i, size_t ri)
  257 {
  258   return i < ri ? i : i+1;
  259 }
  260 
  261 bool application::matchSignature(env &e, types::signature *source,
  262                                  arglist &al) {
  263   formal_vector &f=source->formals;
  264 
  265 #if 0
  266   cout << "num args: " << f.size() << endl;
  267   cout << "num keyword-only: " << sig->numKeywordOnly << endl;
  268 #endif
  269 
  270   size_t ri = al.rest.val ? al.restPosition : f.size();
  271 
  272   // First, match all of the named (non-rest) arguments.
  273   for (size_t i=0; i<f.size(); ++i)
  274     if (f[i].name)
  275       if (!matchNamedArgument(e, f[i], al[i].val, adjustIndex(i,ri)))
  276         return false;
  277 
  278   // Then, the unnamed.
  279   for (size_t i=0; i<f.size(); ++i)
  280     if (!f[i].name)
  281       if (!matchArgument(e, f[i], al[i].val, adjustIndex(i,ri)))
  282         return false;
  283 
  284   // Then, the rest argument.
  285   if (source->hasRest())
  286     if (!matchRest(e, source->getRest(), al.rest.val, ri))
  287       return false;
  288 
  289   // Fill in any remaining arguments with their defaults.
  290   return complete();
  291 }
  292        
  293 bool application::matchOpen(env &e, signature *source, arglist &al) {
  294   assert(rest);
  295 
  296   // Pack all given parameters into the rest argument.
  297   formal_vector &f=source->formals;
  298   for (size_t i = 0; i < f.size(); ++i)
  299     if (al[i].name)
  300       // Named arguments are not handled by open signatures.
  301       return false;
  302     else
  303       rest->add(seq.addArg(al[i].val, f[i].t, i));
  304 
  305   if (source->hasRest())
  306     rest->addRest(new varinitArg(al.rest.val, source->getRest().t));
  307 
  308   return true;
  309 }
  310 
  311 application *application::match(env &e, function *t, signature *source,
  312                                 arglist &al) {
  313   assert(t->kind==ty_function);
  314   application *app=new application(t);
  315 
  316   bool success = t->getSignature()->isOpen ?
  317                      app->matchOpen(e, source, al) :
  318                      app->matchSignature(e, source, al);
  319 
  320   //cout << "MATCH " << success << endl;
  321 
  322   return success ? app : 0;
  323 }
  324 
  325 void application::transArgs(coenv &e) {
  326   temp_vector temps;
  327 
  328   for(arg_vector::iterator a=args.begin(); a != args.end(); ++a)
  329     (*a)->trans(e,temps);
  330 
  331   if (rest)
  332     rest->trans(e,temps);
  333 }
  334 
  335 bool application::exact() {
  336   if (sig->isOpen)
  337     return false;
  338   for (score_vector::iterator p = scores.begin(); p != scores.end(); ++p)
  339     if (*p != EXACT)
  340       return false;
  341   return true;
  342 }
  343 
  344 bool application::halfExact() {
  345   if (sig->isOpen)
  346     return false;
  347   if (scores.size() != 2)
  348     return false;
  349   if (scores[0] == EXACT && scores[1] == CAST)
  350     return true;
  351   if (scores[0] == CAST && scores[1] == EXACT)
  352     return true;
  353   return false;
  354 }
  355 
  356 // True if any of the formals have names.
  357 bool namedFormals(signature *sig)
  358 {
  359   formal_vector& formals = sig->formals;
  360   size_t n = formals.size();
  361   for (size_t i = 0; i < n; ++i) {
  362     if (formals[i].name)
  363       return true;
  364   }
  365   return false;
  366 }
  367 
  368 // Tests if arguments in the source signature can be matched to the formals
  369 // in the target signature with no casting or packing.
  370 // This allows overloaded args, but not named args.
  371 bool exactMightMatch(signature *target, signature *source)
  372 {
  373   // Open signatures never exactly match.
  374   if (target->isOpen)
  375     return false;
  376 
  377 #if 0
  378   assert(!namedFormals(source));
  379 #endif
  380 
  381   formal_vector& formals = target->formals;
  382   formal_vector& args = source->formals;
  383 
  384   // Sizes of the two lists.
  385   size_t fn = formals.size(), an = args.size();
  386 
  387   // Indices for the two lists.
  388   size_t fi = 0, ai = 0;
  389 
  390   while (fi < fn && ai < an) {
  391     if (equivalent(formals[fi].t, args[ai].t)) {
  392       // Arguments match, move to the next.
  393       ++fi; ++ai;
  394     } else if (formals[fi].defval) {
  395       // Match formal to default value.
  396       ++fi;
  397     } else {
  398       // Failed to match formal.
  399       return false;
  400     }
  401   }
  402 
  403   assert(fi == fn || ai == an);
  404 
  405   // Packing array arguments into the rest formal is inexact.  Do not allow it
  406   // here.
  407   if (ai < an)
  408     return false;
  409 
  410   assert(ai == an);
  411 
  412   // Match any remaining formal to defaults.
  413   while (fi < fn)
  414     if (formals[fi].defval) {
  415       // Match formal to default value.
  416       ++fi;
  417     } else {
  418       // Failed to match formal.
  419       return false;
  420     }
  421 
  422   // Non-rest arguments have matched.
  423   assert(fi == fn && ai == an);
  424 
  425   // Try to match the rest argument if given.
  426   if (source->hasRest()) {
  427     if (!target->hasRest())
  428       return false;
  429     
  430     if (!equivalent(source->getRest().t, target->getRest().t))
  431       return false;
  432   }
  433 
  434   // All arguments have matched.
  435   return true;
  436 }
  437 
  438 // Tries to match applications without casting.  If an application matches
  439 // here, we need not attempt to match others with the slower, more general
  440 // techniques.
  441 app_list exactMultimatch(env &e,
  442                          types::overloaded *o,
  443                          types::signature *source,
  444                          arglist &al)
  445 {
  446   assert(source);
  447 
  448   app_list l;
  449 
  450   // This can't handle named arguments.
  451   if (namedFormals(source))
  452     return l; /* empty */
  453 
  454   for (ty_vector::iterator t=o->sub.begin(); t!=o->sub.end(); ++t)
  455   {
  456     if ((*t)->kind != ty_function)
  457       continue;
  458 
  459     function *ft = (function *)*t;
  460 
  461     // First we run a test to see if all arguments could be exactly matched.
  462     // If this returns false, no such match is possible.
  463     // If it returns true, an exact match may or may not be possible.
  464     if (!exactMightMatch(ft->getSignature(), source))
  465       continue;
  466 
  467     application *a=application::match(e, ft, source, al);
  468 
  469     // Consider calling
  470     //   void f(A a=new A, int y)
  471     // with
  472     //   f(3)
  473     // This matches exactly if there is no implicit cast from int to A.
  474     // Otherwise, it does not match.
  475     // Thus, there is no way to know if the
  476     // match truly is exact without looking at the environment.
  477     // In such a case, exactMightMatch() must return true, but there is no
  478     // exact match.  Such false positives are eliminated here.
  479     // 
  480     // Consider calling
  481     //   void f(int x, real y=0.0, int z=0)
  482     // with
  483     //   f(1,2)
  484     // exactMightMatch() will return true, matching 1 to x and 2 to z, but the
  485     // application::match will give an inexact match of 1 to x to 2 to y, due
  486     // to the cast from int to real.  Therefore, we must test for exactness
  487     // even after matching.
  488     if (a && a->exact())
  489       l.push_back(a);
  490   }
  491 
  492   //cout << "EXACTMATCH " << (!l.empty()) << endl;
  493   return l;
  494 }
  495 
  496 bool halfExactMightMatch(env &e,
  497                          signature *target, types::ty *t1, types::ty *t2)
  498 {
  499   formal_vector& formals = target->formals;
  500   if (formals.size() < 2)
  501     return false;
  502   if (formals.size() > 2) {
  503     // We should probably abort the whole matching in this case.  For now,
  504     // return true and let the usual matching handle it.
  505     return true;
  506   }
  507 
  508   assert(formals[0].t);
  509   assert(formals[1].t);
  510 
  511   // These casting tests if successful will be repeated again by
  512   // application::match.  It would be nice to avoid this somehow, but the
  513   // additional complexity is probably not worth the minor speed improvement.
  514   if (equivalent(formals[0].t, t1))
  515      return e.fastCastable(formals[1].t, t2);
  516   else 
  517     return equivalent(formals[1].t, t2) && e.fastCastable(formals[0].t, t1);
  518 }
  519 
  520 // Most common after exact matches are cases such as
  521 //   2 + 3.4   (int, real) --> (real, real)
  522 // that is, binary operations where one of the operands matches exactly and the
  523 // other does not.  This function searches for these so-called "half-exact"
  524 // matches.  This should only be called after exactMultimatch has failed.
  525 app_list halfExactMultimatch(env &e,
  526                              types::overloaded *o,
  527                              types::signature *source,
  528                              arglist &al)
  529 {
  530   assert(source);
  531 
  532   app_list l;
  533 
  534 
  535   // Half exact is only in the case of two arguments.
  536   formal_vector& formals = source->formals;
  537   if (formals.size() != 2 || source->hasRest())
  538     return l; /* empty */
  539 
  540   // This can't handle named arguments.
  541   if (namedFormals(source))
  542     return l; /* empty */
  543 
  544   // Alias the two argument types.
  545   types::ty *t1 = formals[0].t;
  546   types::ty *t2 = formals[1].t;
  547 
  548   assert(t1); assert(t2);
  549 
  550   for (ty_vector::iterator t=o->sub.begin(); t!=o->sub.end(); ++t)
  551   {
  552     if ((*t)->kind != ty_function)
  553       continue;
  554 
  555     function *ft = (function *)*t;
  556 
  557 #if 1
  558     if (!halfExactMightMatch(e, ft->getSignature(), t1, t2))
  559       continue;
  560 #endif
  561 
  562     application *a=application::match(e, ft, source, al);
  563 
  564 #if 1
  565     if (a && a->halfExact())
  566       l.push_back(a);
  567 #endif
  568   }
  569 
  570   return l;
  571 }
  572 
  573 // Simple check if there are too many arguments to match the candidate
  574 // function.
  575 // A "tooFewArgs" variant was also implemented at some point, but did
  576 // not give any speed-up.
  577 bool tooManyArgs(types::signature *target, types::signature *source) {
  578   return source->getNumFormals() > target->getNumFormals() &&
  579          !target->hasRest();
  580 }
  581 
  582 // The full overloading resolution system, which handles casting of arguments,
  583 // packing into rest arguments, named arguments, etc.
  584 app_list inexactMultimatch(env &e,
  585                            types::overloaded *o,
  586                            types::signature *source,
  587                            arglist &al)
  588 {
  589   assert(source);
  590 
  591   app_list l;
  592 
  593 
  594 #define DEBUG_GETAPP 0
  595 #if DEBUG_GETAPP
  596   //cout << "source: " << *source << endl;
  597   //cout << "ARGS: " << source->getNumFormals() << endl;
  598   bool perfect=false;
  599   bool exact=false;
  600   bool halfExact=false;
  601 #endif
  602 
  603   for(ty_vector::iterator t=o->sub.begin(); t!=o->sub.end(); ++t) {
  604     if ((*t)->kind==ty_function) {
  605 #if DEBUG_GETAPP
  606       function *ft = dynamic_cast<function *>(*t);
  607       signature *target = ft->getSignature();
  608       if (equivalent(target, source))
  609         perfect = true;
  610 #endif
  611 
  612       // Check if there are two many arguments to match.
  613       if (tooManyArgs((*t)->getSignature(), source))
  614         continue;
  615 
  616       application *a=application::match(e, (function *)(*t), source, al);
  617       if (a)
  618         l.push_back(a);
  619 
  620 #if DEBUG_GETAPP
  621       if (a && !namedFormals(source)) {
  622         assert(a->exact() == exactlyMatchable(ft->getSignature(), source));
  623         if (a->halfExact() && !namedFormals(source)) {
  624           assert(halfExactMightMatch(e, target, source->getFormal(0).t,
  625                                                 source->getFormal(1).t));
  626         }
  627           
  628       }
  629       if (a && a->exact())
  630         exact = true;
  631       if (a && a->halfExact())
  632         halfExact = true;
  633 #endif
  634     }
  635   }
  636 
  637 #if DEBUG_GETAPP
  638   cout << (perfect     ? "PERFECT" :
  639            exact       ? "EXACT" :
  640            halfExact   ? "HALFEXACT" :
  641                          "IMPERFECT")
  642        << endl;
  643 #endif
  644 
  645   if (l.size() > 1) {
  646     // Return the most specific candidates.
  647     maximizer m;
  648     for (app_list::iterator x=l.begin(); x!=l.end(); ++x) {
  649       assert(*x);
  650       m.add(*x);
  651     }
  652     return m.result();
  653   }
  654   else
  655     return l;
  656 }
  657 
  658 enum testExactType {
  659   TEST_EXACT,
  660   DONT_TEST_EXACT,
  661 };
  662 
  663 // Sanity check for multimatch optimizations.
  664 void sameApplications(app_list a, app_list b, testExactType te) {
  665   assert(a.size() == b.size());
  666 
  667   if (te == TEST_EXACT) {
  668     for (app_list::iterator i = a.begin(); i != a.end(); ++i) {
  669       if (!(*i)->exact()) {
  670         cout << *(*i)->getType() << endl;
  671       }
  672       assert((*i)->exact());
  673     }
  674     for (app_list::iterator i = b.begin(); i != b.end(); ++i)
  675       assert((*i)->exact());
  676   }
  677 
  678   if (a.size() == 1)
  679     assert(equivalent(a.front()->getType(), b.front()->getType()));
  680 }
  681 
  682 app_list multimatch(env &e,
  683                     types::overloaded *o,
  684                     types::signature *source,
  685                     arglist &al)
  686 {
  687   app_list a = exactMultimatch(e, o, source, al);
  688   if (!a.empty()) {
  689 #if DEBUG_CACHE
  690     // Make sure that exactMultimatch and the fallback return the same
  691     // application(s).
  692     sameApplications(a, inexactMultimatch(e, o, source, al), TEST_EXACT);
  693 #endif
  694 
  695     return a;
  696   }
  697 
  698   a = halfExactMultimatch(e, o, source, al);
  699   if (!a.empty()) {
  700 #if DEBUG_CACHE
  701     sameApplications(a, inexactMultimatch(e, o, source, al), DONT_TEST_EXACT);
  702 #endif
  703 
  704     return a;
  705   }
  706 
  707   // Slow but most general method.
  708   return inexactMultimatch(e, o, source, al);
  709 }
  710 
  711 } // namespace trans