1 /***** 2 * application.h 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 #ifndef APPLICATION_H 12 #define APPLICATION_H 13 14 #include "common.h" 15 #include "types.h" 16 #include "coenv.h" 17 #include "exp.h" 18 19 // Defined in runtime.in: 20 namespace run { 21 void pushDefault(vm::stack *Stack); 22 } 23 24 using absyntax::arglist; 25 using absyntax::varinit; 26 using absyntax::arrayinit; 27 using absyntax::tempExp; 28 29 // This is mid-way between trans and absyntax. 30 namespace trans { 31 32 typedef Int score; 33 34 typedef mem::vector<score> score_vector; 35 36 // This is used during the translation of arguments to store temporary 37 // expressions for arguments that need to be translated for side-effects at a 38 // certain point but used later on. The invariant maintained is that if the 39 // vector has n elements, then the side-effects for the first n arguments have 40 // been translated. Null is pushed onto the vector to indicate that the 41 // expression was evaluated directly onto the stack, without the use of a 42 // temporary. 43 typedef mem::vector<tempExp *> temp_vector; 44 45 struct arg : public gc { 46 types::ty *t; 47 argarg48 arg(types::ty *t) 49 : t(t) {} ~argarg50 virtual ~arg() {} 51 52 virtual void trans(coenv &e, temp_vector &) = 0; 53 }; 54 55 struct varinitArg : public arg { 56 varinit *v; 57 varinitArgvarinitArg58 varinitArg(varinit *v, types::ty *t) 59 : arg(t), v(v) {} 60 transvarinitArg61 virtual void trans(coenv &e, temp_vector &) { 62 // Open signatures can match overloaded variables, but there is no way to 63 // translate the result, so report an error. 64 if (t->kind == types::ty_overloaded) { 65 em.error(v->getPos()); 66 em << "overloaded argument in function call"; 67 } 68 else 69 v->transToType(e, t); 70 } 71 }; 72 73 74 // Pushes a default argument token on the stack as a placeholder for the 75 // argument. 76 struct defaultArg : public arg { defaultArgdefaultArg77 defaultArg(types::ty *t) 78 : arg(t) {} 79 transdefaultArg80 virtual void trans(coenv &e, temp_vector &) { 81 //e.c.encode(inst::builtin, run::pushDefault); 82 e.c.encode(inst::push_default); 83 } 84 }; 85 86 // Handles translation of all the arguments matched to the rest formal. 87 // NOTE: This code duplicates a lot of arrayinit. 88 struct restArg : public gc { 89 mem::list<arg *> inits; 90 91 arg *rest; 92 public: restArgrestArg93 restArg() 94 : rest(0) {} 95 ~restArgrestArg96 virtual ~restArg() 97 {} 98 99 // Encodes the instructions to make an array from size elements on the stack. 100 static void transMaker(coenv &e, Int size, bool rest); 101 102 void trans(coenv &e, temp_vector &temps); 103 addrestArg104 void add(arg *init) { 105 inits.push_back(init); 106 } 107 addRestrestArg108 void addRest(arg *init) { 109 rest=init; 110 } 111 }; 112 113 // This class generates sequenced args, args whose side-effects occur in order 114 // according to their index, regardless of the order they are called. This is 115 // used to ensure left-to-right order of evaluation of keyword arguments, even 116 // if they are given out of the order specified in the declaration. 117 class sequencer { 118 struct sequencedArg : public varinitArg { 119 sequencer &parent; 120 size_t i; sequencedArgsequencedArg121 sequencedArg(varinit *v, types::ty *t, sequencer &parent, size_t i) 122 : varinitArg(v, t), parent(parent), i(i) {} 123 transsequencedArg124 void trans(coenv &e, temp_vector &temps) { 125 parent.trans(e, i, temps); 126 } 127 }; 128 129 typedef mem::vector<sequencedArg *> sa_vector; 130 sa_vector args; 131 132 // Makes a temporary for the next argument in the sequence. alias(coenv & e,temp_vector & temps)133 void alias(coenv &e, temp_vector &temps) { 134 size_t n=temps.size(); 135 assert(n < args.size()); 136 sequencedArg *sa=args[n]; 137 assert(sa); 138 139 temps.push_back(new tempExp(e, sa->v, sa->t)); 140 } 141 142 // Get in a state to translate the i-th argument, aliasing any arguments that 143 // occur before it in the sequence. advance(coenv & e,size_t i,temp_vector & temps)144 void advance(coenv &e, size_t i, temp_vector &temps) { 145 while (temps.size() < i) 146 alias(e,temps); 147 } 148 trans(coenv & e,size_t i,temp_vector & temps)149 void trans(coenv &e, size_t i, temp_vector &temps) { 150 if (i < temps.size()) { 151 // Already translated, use the alias. 152 assert(temps[i]); 153 temps[i]->trans(e); 154 } 155 else { 156 // Alias earlier args if necessary. 157 advance(e, i, temps); 158 159 // Translate using the base method. 160 args[i]->varinitArg::trans(e,temps); 161 162 // Push null to indicate the argument has been translated. 163 temps.push_back(0); 164 } 165 } 166 167 public: addArg(varinit * v,types::ty * t,size_t i)168 arg *addArg(varinit *v, types::ty *t, size_t i) { 169 if (args.size() <= i) 170 args.resize(i+1); 171 return args[i]=new sequencedArg(v, t, *this, i); 172 } 173 }; 174 175 176 class application : public gc { 177 types::signature *sig; 178 types::function *t; 179 180 // Sequencer to ensure given arguments are evaluated in the proper order. 181 // Use of this sequencer means that transArgs can only be called once. 182 sequencer seq; 183 184 typedef mem::vector<arg *> arg_vector; 185 arg_vector args; 186 restArg *rest; 187 188 // Target formal to match with arguments to be packed into the rest array. 189 types::formal rf; 190 191 // During the matching of arguments to an application, this stores the index 192 // of the first unmatched formal. 193 size_t index; 194 195 // To resolve which is the best application in case of multiple matches of 196 // overloaded functions, a score is kept for every source argument matched, 197 // and an application with higher-scoring matches is chosen. 198 score_vector scores; 199 200 void initRest(); 201 application(types::signature * sig)202 application(types::signature *sig) 203 : sig(sig), 204 t(0), 205 args(sig->formals.size()), 206 rest(0), 207 rf(0), 208 index(0) 209 { assert(sig); initRest(); } 210 application(types::function * t)211 application(types::function *t) 212 : sig(t->getSignature()), 213 t(t), 214 args(sig->formals.size()), 215 rest(0), 216 rf(0), 217 index(0) 218 { assert(sig); initRest(); } 219 getTarget()220 types::formal &getTarget() { 221 return sig->getFormal(index); 222 } 223 224 // Move the index forward one, then keep going until we're at an unmatched 225 // argument. advanceIndex()226 void advanceIndex() { 227 do { 228 ++index; 229 } while (index < args.size() && args[index]!=0); 230 } 231 232 // Finds the first unmatched formal of the given name, returning the index. 233 // The rest formal is not tested. This function returns FAIL if no formals 234 // match. 235 Int find(symbol name); 236 237 // Match the formal at index to its default argument (if it has one). 238 bool matchDefault(); 239 240 // Match the argument to the formal indexed by spot. 241 bool matchAtSpot(size_t spot, env &e, types::formal &source, 242 varinit *a, size_t evalIndex); 243 244 // Match the argument to be packed into the rest array, if possible. 245 bool matchArgumentToRest(env &e, types::formal& source, 246 varinit *a, size_t evalIndex); 247 248 // Matches the argument to a formal in the target signature (possibly causing 249 // other formals in the target to be matched to default values), and updates 250 // the matchpoint accordingly. 251 bool matchArgument(env &e, types::formal& source, 252 varinit *a, size_t evalIndex); 253 254 // Match an argument bound to a name, as in f(index=7). 255 bool matchNamedArgument(env &e, types::formal& source, 256 varinit *a, size_t evalIndex); 257 258 // After all source formals have been matched, checks if the match is 259 // complete (filling in final default values if necessary). 260 bool complete(); 261 262 // Match a rest argument in the calling expression. 263 bool matchRest(env &e, types::formal& f, varinit *a, size_t evalIndex); 264 265 // Match the argument represented in signature to the target signature. On 266 // success, all of the arguments in args will be properly set up. 267 bool matchSignature(env &e, types::signature *source, arglist &al); 268 269 // Match a signature which is open, meaning that any sequence of arguments is 270 // matched. 271 bool matchOpen(env &e, signature *source, arglist &al); 272 273 friend class maximizer; 274 public: 275 // Attempt to build an application given the target signature and the source 276 // signature (representing the given arguments). Return 0 if they cannot be 277 // matched. 278 static application *match(env &e, 279 types::function *t, 280 types::signature *source, 281 arglist &al); 282 283 // Translate the arguments so they appear in order on the stack in 284 // preparation for a call. 285 void transArgs(coenv &e); 286 getType()287 types::function *getType() { 288 return t; 289 } 290 291 // This returns true in the special case that the arguments matched without 292 // casting or packing into the rest formal. 293 bool exact(); 294 295 // The next best thing (score-wise) to an exact match. This returns true if 296 // there are two arguments, one of which is cast and one is matched exactly 297 // and neither are packed into the rest argument. 298 bool halfExact(); 299 }; 300 301 typedef mem::list<application *> app_list; 302 303 // Given an overloaded list of types, determines which type to call. If none 304 // are applicable, returns an empty vector, if there is ambiguity, several will 305 // be returned. 306 app_list multimatch(env &e, 307 types::overloaded *o, 308 types::signature *source, 309 arglist &al); 310 311 } // namespace trans 312 313 #endif 314