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