1 | // |
---|
2 | // Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo |
---|
3 | // |
---|
4 | // The contents of this file are covered under the licence agreement in the |
---|
5 | // file "LICENCE" distributed with Cforall. |
---|
6 | // |
---|
7 | // AlternativeFinder.cc -- |
---|
8 | // |
---|
9 | // Author : Richard C. Bilson |
---|
10 | // Created On : Sat May 16 23:52:08 2015 |
---|
11 | // Last Modified By : Peter A. Buhr |
---|
12 | // Last Modified On : Sat Feb 17 11:19:39 2018 |
---|
13 | // Update Count : 33 |
---|
14 | // |
---|
15 | |
---|
16 | #include <algorithm> // for copy |
---|
17 | #include <cassert> // for strict_dynamic_cast, assert, assertf |
---|
18 | #include <cstddef> // for size_t |
---|
19 | #include <iostream> // for operator<<, cerr, ostream, endl |
---|
20 | #include <iterator> // for back_insert_iterator, back_inserter |
---|
21 | #include <list> // for _List_iterator, list, _List_const_... |
---|
22 | #include <map> // for _Rb_tree_iterator, map, _Rb_tree_c... |
---|
23 | #include <memory> // for allocator_traits<>::value_type, unique_ptr |
---|
24 | #include <utility> // for pair |
---|
25 | #include <vector> // for vector |
---|
26 | |
---|
27 | #include "Alternative.h" // for AltList, Alternative |
---|
28 | #include "AlternativeFinder.h" |
---|
29 | #include "Common/SemanticError.h" // for SemanticError |
---|
30 | #include "Common/utility.h" // for deleteAll, printAll, CodeLocation |
---|
31 | #include "Cost.h" // for Cost, Cost::zero, operator<<, Cost... |
---|
32 | #include "ExplodedActual.h" // for ExplodedActual |
---|
33 | #include "InitTweak/InitTweak.h" // for getFunctionName |
---|
34 | #include "RenameVars.h" // for RenameVars, global_renamer |
---|
35 | #include "ResolveTypeof.h" // for resolveTypeof |
---|
36 | #include "Resolver.h" // for resolveStmtExpr |
---|
37 | #include "SymTab/Indexer.h" // for Indexer |
---|
38 | #include "SymTab/Mangler.h" // for Mangler |
---|
39 | #include "SymTab/Validate.h" // for validateType |
---|
40 | #include "SynTree/Constant.h" // for Constant |
---|
41 | #include "SynTree/Declaration.h" // for DeclarationWithType, TypeDecl, Dec... |
---|
42 | #include "SynTree/Expression.h" // for Expression, CastExpr, NameExpr |
---|
43 | #include "SynTree/Initializer.h" // for SingleInit, operator<<, Designation |
---|
44 | #include "SynTree/SynTree.h" // for UniqueId |
---|
45 | #include "SynTree/Type.h" // for Type, FunctionType, PointerType |
---|
46 | #include "Tuples/Explode.h" // for explode |
---|
47 | #include "Tuples/Tuples.h" // for isTtype, handleTupleAssignment |
---|
48 | #include "Unify.h" // for unify |
---|
49 | #include "typeops.h" // for adjustExprType, polyCost, castCost |
---|
50 | |
---|
51 | bool resolvep; |
---|
52 | #define PRINT( text ) if ( resolvep ) { text } |
---|
53 | //#define DEBUG_COST |
---|
54 | |
---|
55 | using std::move; |
---|
56 | |
---|
57 | /// copies any copyable type |
---|
58 | template<typename T> |
---|
59 | T copy(const T& x) { return x; } |
---|
60 | |
---|
61 | namespace ResolvExpr { |
---|
62 | struct AlternativeFinder::Finder : public WithShortCircuiting { |
---|
63 | Finder( AlternativeFinder & altFinder ) : altFinder( altFinder ), indexer( altFinder.indexer ), alternatives( altFinder.alternatives ), env( altFinder.env ), targetType( altFinder.targetType ) {} |
---|
64 | |
---|
65 | void previsit( BaseSyntaxNode * ) { visit_children = false; } |
---|
66 | |
---|
67 | void postvisit( ApplicationExpr * applicationExpr ); |
---|
68 | void postvisit( UntypedExpr * untypedExpr ); |
---|
69 | void postvisit( AddressExpr * addressExpr ); |
---|
70 | void postvisit( LabelAddressExpr * labelExpr ); |
---|
71 | void postvisit( CastExpr * castExpr ); |
---|
72 | void postvisit( VirtualCastExpr * castExpr ); |
---|
73 | void postvisit( UntypedMemberExpr * memberExpr ); |
---|
74 | void postvisit( MemberExpr * memberExpr ); |
---|
75 | void postvisit( NameExpr * variableExpr ); |
---|
76 | void postvisit( VariableExpr * variableExpr ); |
---|
77 | void postvisit( ConstantExpr * constantExpr ); |
---|
78 | void postvisit( SizeofExpr * sizeofExpr ); |
---|
79 | void postvisit( AlignofExpr * alignofExpr ); |
---|
80 | void postvisit( UntypedOffsetofExpr * offsetofExpr ); |
---|
81 | void postvisit( OffsetofExpr * offsetofExpr ); |
---|
82 | void postvisit( OffsetPackExpr * offsetPackExpr ); |
---|
83 | void postvisit( AttrExpr * attrExpr ); |
---|
84 | void postvisit( LogicalExpr * logicalExpr ); |
---|
85 | void postvisit( ConditionalExpr * conditionalExpr ); |
---|
86 | void postvisit( CommaExpr * commaExpr ); |
---|
87 | void postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ); |
---|
88 | void postvisit( ConstructorExpr * ctorExpr ); |
---|
89 | void postvisit( RangeExpr * rangeExpr ); |
---|
90 | void postvisit( UntypedTupleExpr * tupleExpr ); |
---|
91 | void postvisit( TupleExpr * tupleExpr ); |
---|
92 | void postvisit( TupleIndexExpr * tupleExpr ); |
---|
93 | void postvisit( TupleAssignExpr * tupleExpr ); |
---|
94 | void postvisit( UniqueExpr * unqExpr ); |
---|
95 | void postvisit( StmtExpr * stmtExpr ); |
---|
96 | void postvisit( UntypedInitExpr * initExpr ); |
---|
97 | void postvisit( InitExpr * initExpr ); |
---|
98 | void postvisit( DeletedExpr * delExpr ); |
---|
99 | void postvisit( GenericExpr * genExpr ); |
---|
100 | |
---|
101 | /// Adds alternatives for anonymous members |
---|
102 | void addAnonConversions( const Alternative & alt ); |
---|
103 | /// Adds alternatives for member expressions, given the aggregate, conversion cost for that aggregate, and name of the member |
---|
104 | template< typename StructOrUnionType > void addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, const std::string & name ); |
---|
105 | /// Adds alternatives for member expressions where the left side has tuple type |
---|
106 | void addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ); |
---|
107 | /// Adds alternatives for offsetof expressions, given the base type and name of the member |
---|
108 | template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name ); |
---|
109 | /// Takes a final result and checks if its assertions can be satisfied |
---|
110 | template<typename OutputIterator> |
---|
111 | void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out ); |
---|
112 | /// Finds matching alternatives for a function, given a set of arguments |
---|
113 | template<typename OutputIterator> |
---|
114 | void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out ); |
---|
115 | /// Checks if assertion parameters match for a new alternative |
---|
116 | template< typename OutputIterator > |
---|
117 | void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ); |
---|
118 | private: |
---|
119 | AlternativeFinder & altFinder; |
---|
120 | const SymTab::Indexer &indexer; |
---|
121 | AltList & alternatives; |
---|
122 | const TypeEnvironment &env; |
---|
123 | Type *& targetType; |
---|
124 | }; |
---|
125 | |
---|
126 | Cost sumCost( const AltList &in ) { |
---|
127 | Cost total = Cost::zero; |
---|
128 | for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) { |
---|
129 | total += i->cost; |
---|
130 | } |
---|
131 | return total; |
---|
132 | } |
---|
133 | |
---|
134 | void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt ) { |
---|
135 | Indenter indent = { Indenter::tabsize, indentAmt }; |
---|
136 | for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) { |
---|
137 | i->print( os, indent ); |
---|
138 | os << std::endl; |
---|
139 | } |
---|
140 | } |
---|
141 | |
---|
142 | namespace { |
---|
143 | void makeExprList( const AltList &in, std::list< Expression* > &out ) { |
---|
144 | for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) { |
---|
145 | out.push_back( i->expr->clone() ); |
---|
146 | } |
---|
147 | } |
---|
148 | |
---|
149 | struct PruneStruct { |
---|
150 | bool isAmbiguous; |
---|
151 | AltList::iterator candidate; |
---|
152 | PruneStruct() {} |
---|
153 | PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {} |
---|
154 | }; |
---|
155 | |
---|
156 | /// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations |
---|
157 | template< typename InputIterator, typename OutputIterator > |
---|
158 | void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out ) { |
---|
159 | // select the alternatives that have the minimum conversion cost for a particular set of result types |
---|
160 | std::map< std::string, PruneStruct > selected; |
---|
161 | for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) { |
---|
162 | PruneStruct current( candidate ); |
---|
163 | std::string mangleName; |
---|
164 | { |
---|
165 | Type * newType = candidate->expr->get_result()->clone(); |
---|
166 | candidate->env.apply( newType ); |
---|
167 | mangleName = SymTab::Mangler::mangle( newType ); |
---|
168 | delete newType; |
---|
169 | } |
---|
170 | std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName ); |
---|
171 | if ( mapPlace != selected.end() ) { |
---|
172 | if ( candidate->cost < mapPlace->second.candidate->cost ) { |
---|
173 | PRINT( |
---|
174 | std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl; |
---|
175 | ) |
---|
176 | selected[ mangleName ] = current; |
---|
177 | } else if ( candidate->cost == mapPlace->second.candidate->cost ) { |
---|
178 | // if one of the candidates contains a deleted identifier, can pick the other, since |
---|
179 | // deleted expressions should not be ambiguous if there is another option that is at least as good |
---|
180 | if ( findDeletedExpr( candidate->expr ) ) { |
---|
181 | // do nothing |
---|
182 | PRINT( std::cerr << "candidate is deleted" << std::endl; ) |
---|
183 | } else if ( findDeletedExpr( mapPlace->second.candidate->expr ) ) { |
---|
184 | PRINT( std::cerr << "current is deleted" << std::endl; ) |
---|
185 | selected[ mangleName ] = current; |
---|
186 | } else { |
---|
187 | PRINT( |
---|
188 | std::cerr << "marking ambiguous" << std::endl; |
---|
189 | ) |
---|
190 | mapPlace->second.isAmbiguous = true; |
---|
191 | } |
---|
192 | } else { |
---|
193 | PRINT( |
---|
194 | std::cerr << "cost " << candidate->cost << " loses to " << mapPlace->second.candidate->cost << std::endl; |
---|
195 | ) |
---|
196 | } |
---|
197 | } else { |
---|
198 | selected[ mangleName ] = current; |
---|
199 | } |
---|
200 | } |
---|
201 | |
---|
202 | // accept the alternatives that were unambiguous |
---|
203 | for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) { |
---|
204 | if ( ! target->second.isAmbiguous ) { |
---|
205 | Alternative &alt = *target->second.candidate; |
---|
206 | alt.env.applyFree( alt.expr->get_result() ); |
---|
207 | *out++ = alt; |
---|
208 | } |
---|
209 | } |
---|
210 | } |
---|
211 | |
---|
212 | void renameTypes( Expression *expr ) { |
---|
213 | renameTyVars( expr->result ); |
---|
214 | } |
---|
215 | } // namespace |
---|
216 | |
---|
217 | void referenceToRvalueConversion( Expression *& expr, Cost & cost ) { |
---|
218 | if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) { |
---|
219 | // cast away reference from expr |
---|
220 | expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() ); |
---|
221 | cost.incReference(); |
---|
222 | } |
---|
223 | } |
---|
224 | |
---|
225 | template< typename InputIterator, typename OutputIterator > |
---|
226 | void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) { |
---|
227 | while ( begin != end ) { |
---|
228 | AlternativeFinder finder( indexer, env ); |
---|
229 | finder.findWithAdjustment( *begin ); |
---|
230 | // XXX either this |
---|
231 | //Designators::fixDesignations( finder, (*begin++)->get_argName() ); |
---|
232 | // or XXX this |
---|
233 | begin++; |
---|
234 | PRINT( |
---|
235 | std::cerr << "findSubExprs" << std::endl; |
---|
236 | printAlts( finder.alternatives, std::cerr ); |
---|
237 | ) |
---|
238 | *out++ = finder; |
---|
239 | } |
---|
240 | } |
---|
241 | |
---|
242 | AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env ) |
---|
243 | : indexer( indexer ), env( env ) { |
---|
244 | } |
---|
245 | |
---|
246 | void AlternativeFinder::find( Expression *expr, bool adjust, bool prune, bool failFast ) { |
---|
247 | PassVisitor<Finder> finder( *this ); |
---|
248 | expr->accept( finder ); |
---|
249 | if ( failFast && alternatives.empty() ) { |
---|
250 | PRINT( |
---|
251 | std::cerr << "No reasonable alternatives for expression " << expr << std::endl; |
---|
252 | ) |
---|
253 | SemanticError( expr, "No reasonable alternatives for expression " ); |
---|
254 | } |
---|
255 | if ( prune ) { |
---|
256 | auto oldsize = alternatives.size(); |
---|
257 | PRINT( |
---|
258 | std::cerr << "alternatives before prune:" << std::endl; |
---|
259 | printAlts( alternatives, std::cerr ); |
---|
260 | ) |
---|
261 | AltList pruned; |
---|
262 | pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) ); |
---|
263 | if ( failFast && pruned.empty() ) { |
---|
264 | std::ostringstream stream; |
---|
265 | AltList winners; |
---|
266 | findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) ); |
---|
267 | stream << "Cannot choose between " << winners.size() << " alternatives for expression\n"; |
---|
268 | expr->print( stream ); |
---|
269 | stream << " Alternatives are:\n"; |
---|
270 | printAlts( winners, stream, 1 ); |
---|
271 | SemanticError( expr->location, stream.str() ); |
---|
272 | } |
---|
273 | alternatives = move(pruned); |
---|
274 | PRINT( |
---|
275 | std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; |
---|
276 | ) |
---|
277 | PRINT( |
---|
278 | std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl; |
---|
279 | ) |
---|
280 | } |
---|
281 | // adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted |
---|
282 | for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) { |
---|
283 | if ( adjust ) { |
---|
284 | adjustExprType( i->expr->get_result(), i->env, indexer ); |
---|
285 | } |
---|
286 | } |
---|
287 | |
---|
288 | // Central location to handle gcc extension keyword, etc. for all expression types. |
---|
289 | for ( Alternative &iter: alternatives ) { |
---|
290 | iter.expr->set_extension( expr->get_extension() ); |
---|
291 | iter.expr->location = expr->location; |
---|
292 | } // for |
---|
293 | } |
---|
294 | |
---|
295 | void AlternativeFinder::findWithAdjustment( Expression *expr ) { |
---|
296 | find( expr, true ); |
---|
297 | } |
---|
298 | |
---|
299 | void AlternativeFinder::findWithoutPrune( Expression * expr ) { |
---|
300 | find( expr, true, false ); |
---|
301 | } |
---|
302 | |
---|
303 | void AlternativeFinder::maybeFind( Expression * expr ) { |
---|
304 | find( expr, true, true, false ); |
---|
305 | } |
---|
306 | |
---|
307 | void AlternativeFinder::Finder::addAnonConversions( const Alternative & alt ) { |
---|
308 | // adds anonymous member interpretations whenever an aggregate value type is seen. |
---|
309 | // it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value |
---|
310 | std::unique_ptr<Expression> aggrExpr( alt.expr->clone() ); |
---|
311 | alt.env.apply( aggrExpr->result ); |
---|
312 | Type * aggrType = aggrExpr->result; |
---|
313 | if ( dynamic_cast< ReferenceType * >( aggrType ) ) { |
---|
314 | aggrType = aggrType->stripReferences(); |
---|
315 | aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) ); |
---|
316 | } |
---|
317 | |
---|
318 | if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->result ) ) { |
---|
319 | addAggMembers( structInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, "" ); |
---|
320 | } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->result ) ) { |
---|
321 | addAggMembers( unionInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, "" ); |
---|
322 | } // if |
---|
323 | } |
---|
324 | |
---|
325 | template< typename StructOrUnionType > |
---|
326 | void AlternativeFinder::Finder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, const std::string & name ) { |
---|
327 | std::list< Declaration* > members; |
---|
328 | aggInst->lookup( name, members ); |
---|
329 | |
---|
330 | for ( Declaration * decl : members ) { |
---|
331 | if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( decl ) ) { |
---|
332 | // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so |
---|
333 | // can't construct in place and use vector::back |
---|
334 | Alternative newAlt( new MemberExpr( dwt, expr->clone() ), env, newCost ); |
---|
335 | renameTypes( newAlt.expr ); |
---|
336 | addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression. |
---|
337 | alternatives.push_back( std::move(newAlt) ); |
---|
338 | } else { |
---|
339 | assert( false ); |
---|
340 | } |
---|
341 | } |
---|
342 | } |
---|
343 | |
---|
344 | void AlternativeFinder::Finder::addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) { |
---|
345 | if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) { |
---|
346 | // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning |
---|
347 | auto val = constantExpr->intValue(); |
---|
348 | std::string tmp; |
---|
349 | if ( val >= 0 && (unsigned long long)val < tupleType->size() ) { |
---|
350 | alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) ); |
---|
351 | } // if |
---|
352 | } // if |
---|
353 | } |
---|
354 | |
---|
355 | void AlternativeFinder::Finder::postvisit( ApplicationExpr *applicationExpr ) { |
---|
356 | alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) ); |
---|
357 | } |
---|
358 | |
---|
359 | Cost computeConversionCost( Type * actualType, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) { |
---|
360 | PRINT( |
---|
361 | std::cerr << std::endl << "converting "; |
---|
362 | actualType->print( std::cerr, 8 ); |
---|
363 | std::cerr << std::endl << " to "; |
---|
364 | formalType->print( std::cerr, 8 ); |
---|
365 | std::cerr << std::endl << "environment is: "; |
---|
366 | env.print( std::cerr, 8 ); |
---|
367 | std::cerr << std::endl; |
---|
368 | ) |
---|
369 | Cost convCost = conversionCost( actualType, formalType, indexer, env ); |
---|
370 | PRINT( |
---|
371 | std::cerr << std::endl << "cost is " << convCost << std::endl; |
---|
372 | ) |
---|
373 | if ( convCost == Cost::infinity ) { |
---|
374 | return convCost; |
---|
375 | } |
---|
376 | convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) ); |
---|
377 | PRINT( |
---|
378 | std::cerr << "cost with polycost is " << convCost << std::endl; |
---|
379 | ) |
---|
380 | return convCost; |
---|
381 | } |
---|
382 | |
---|
383 | Cost computeExpressionConversionCost( Expression *& actualExpr, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) { |
---|
384 | Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env ); |
---|
385 | |
---|
386 | // if there is a non-zero conversion cost, ignoring poly cost, then the expression requires conversion. |
---|
387 | // ignore poly cost for now, since this requires resolution of the cast to infer parameters and this |
---|
388 | // does not currently work for the reason stated below. |
---|
389 | Cost tmpCost = convCost; |
---|
390 | tmpCost.incPoly( -tmpCost.get_polyCost() ); |
---|
391 | if ( tmpCost != Cost::zero ) { |
---|
392 | Type *newType = formalType->clone(); |
---|
393 | env.apply( newType ); |
---|
394 | actualExpr = new CastExpr( actualExpr, newType ); |
---|
395 | // xxx - SHOULD be able to resolve this cast, but at the moment pointers are not castable to zero_t, but are implicitly convertible. This is clearly |
---|
396 | // inconsistent, once this is fixed it should be possible to resolve the cast. |
---|
397 | // xxx - this isn't working, it appears because type1 (the formal type) is seen as widenable, but it shouldn't be, because this makes the conversion from DT* to DT* since commontype(zero_t, DT*) is DT*, rather than just nothing. |
---|
398 | |
---|
399 | // AlternativeFinder finder( indexer, env ); |
---|
400 | // finder.findWithAdjustment( actualExpr ); |
---|
401 | // assertf( finder.get_alternatives().size() > 0, "Somehow castable expression failed to find alternatives." ); |
---|
402 | // assertf( finder.get_alternatives().size() == 1, "Somehow got multiple alternatives for known cast expression." ); |
---|
403 | // Alternative & alt = finder.get_alternatives().front(); |
---|
404 | // delete actualExpr; |
---|
405 | // actualExpr = alt.expr->clone(); |
---|
406 | } |
---|
407 | return convCost; |
---|
408 | } |
---|
409 | |
---|
410 | Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) { |
---|
411 | ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( alt.expr ); |
---|
412 | PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() ); |
---|
413 | FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() ); |
---|
414 | |
---|
415 | Cost convCost = Cost::zero; |
---|
416 | std::list< DeclarationWithType* >& formals = function->get_parameters(); |
---|
417 | std::list< DeclarationWithType* >::iterator formal = formals.begin(); |
---|
418 | std::list< Expression* >& actuals = appExpr->get_args(); |
---|
419 | |
---|
420 | for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) { |
---|
421 | Type * actualType = (*actualExpr)->get_result(); |
---|
422 | PRINT( |
---|
423 | std::cerr << "actual expression:" << std::endl; |
---|
424 | (*actualExpr)->print( std::cerr, 8 ); |
---|
425 | std::cerr << "--- results are" << std::endl; |
---|
426 | actualType->print( std::cerr, 8 ); |
---|
427 | ) |
---|
428 | if ( formal == formals.end() ) { |
---|
429 | if ( function->get_isVarArgs() ) { |
---|
430 | convCost.incUnsafe(); |
---|
431 | PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; ) |
---|
432 | // convert reference-typed expressions to value-typed expressions |
---|
433 | referenceToRvalueConversion( *actualExpr, convCost ); |
---|
434 | continue; |
---|
435 | } else { |
---|
436 | return Cost::infinity; |
---|
437 | } |
---|
438 | } |
---|
439 | if ( DefaultArgExpr * def = dynamic_cast< DefaultArgExpr * >( *actualExpr ) ) { |
---|
440 | // default arguments should be free - don't include conversion cost. |
---|
441 | // Unwrap them here because they are not relevant to the rest of the system. |
---|
442 | *actualExpr = def->expr; |
---|
443 | ++formal; |
---|
444 | continue; |
---|
445 | } |
---|
446 | Type * formalType = (*formal)->get_type(); |
---|
447 | convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env ); |
---|
448 | ++formal; // can't be in for-loop update because of the continue |
---|
449 | } |
---|
450 | if ( formal != formals.end() ) { |
---|
451 | return Cost::infinity; |
---|
452 | } |
---|
453 | |
---|
454 | for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) { |
---|
455 | convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env ); |
---|
456 | } |
---|
457 | |
---|
458 | return convCost; |
---|
459 | } |
---|
460 | |
---|
461 | /// Adds type variables to the open variable set and marks their assertions |
---|
462 | void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) { |
---|
463 | for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) { |
---|
464 | unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar }; |
---|
465 | for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->assertions.begin(); assert != (*tyvar)->assertions.end(); ++assert ) { |
---|
466 | needAssertions[ *assert ].isUsed = true; |
---|
467 | } |
---|
468 | /// needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() ); |
---|
469 | } |
---|
470 | } |
---|
471 | |
---|
472 | static const int recursionLimit = /*10*/ 4; ///< Limit to depth of recursion satisfaction |
---|
473 | |
---|
474 | void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) { |
---|
475 | for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) { |
---|
476 | if ( i->second.isUsed ) { |
---|
477 | indexer.addId( i->first ); |
---|
478 | } |
---|
479 | } |
---|
480 | } |
---|
481 | |
---|
482 | template< typename ForwardIterator, typename OutputIterator > |
---|
483 | void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, int level, const SymTab::Indexer &indexer, OutputIterator out ) { |
---|
484 | if ( newAlt.cost == Cost::infinity ) return; // don't proceed down this dead end |
---|
485 | if ( begin == end ) { |
---|
486 | if ( newNeed.empty() ) { |
---|
487 | PRINT( |
---|
488 | std::cerr << "all assertions satisfied, output alternative: "; |
---|
489 | newAlt.print( std::cerr ); |
---|
490 | std::cerr << std::endl; |
---|
491 | ); |
---|
492 | *out++ = newAlt; |
---|
493 | return; |
---|
494 | } else if ( level >= recursionLimit ) { |
---|
495 | SemanticError( newAlt.expr->location, "Too many recursive assertions" ); |
---|
496 | } else { |
---|
497 | AssertionSet newerNeed; |
---|
498 | PRINT( |
---|
499 | std::cerr << "recursing with new set:" << std::endl; |
---|
500 | printAssertionSet( newNeed, std::cerr, 8 ); |
---|
501 | ) |
---|
502 | inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, level+1, indexer, out ); |
---|
503 | return; |
---|
504 | } |
---|
505 | } |
---|
506 | |
---|
507 | ForwardIterator cur = begin++; |
---|
508 | if ( ! cur->second.isUsed ) { |
---|
509 | inferRecursive( begin, end, newAlt, openVars, decls, newNeed, level, indexer, out ); |
---|
510 | return; // xxx - should this continue? previously this wasn't here, and it looks like it should be |
---|
511 | } |
---|
512 | DeclarationWithType *curDecl = cur->first; |
---|
513 | |
---|
514 | PRINT( |
---|
515 | std::cerr << "inferRecursive: assertion is "; |
---|
516 | curDecl->print( std::cerr ); |
---|
517 | std::cerr << std::endl; |
---|
518 | ) |
---|
519 | std::list< SymTab::Indexer::IdData > candidates; |
---|
520 | decls.lookupId( curDecl->get_name(), candidates ); |
---|
521 | /// if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; } |
---|
522 | for ( const auto & data : candidates ) { |
---|
523 | DeclarationWithType * candidate = data.id; |
---|
524 | PRINT( |
---|
525 | std::cerr << "inferRecursive: candidate is "; |
---|
526 | candidate->print( std::cerr ); |
---|
527 | std::cerr << std::endl; |
---|
528 | ) |
---|
529 | |
---|
530 | AssertionSet newHave, newerNeed( newNeed ); |
---|
531 | TypeEnvironment newEnv( newAlt.env ); |
---|
532 | OpenVarSet newOpenVars( openVars ); |
---|
533 | Type *adjType = candidate->get_type()->clone(); |
---|
534 | adjustExprType( adjType, newEnv, indexer ); |
---|
535 | renameTyVars( adjType ); |
---|
536 | PRINT( |
---|
537 | std::cerr << "unifying "; |
---|
538 | curDecl->get_type()->print( std::cerr ); |
---|
539 | std::cerr << " with "; |
---|
540 | adjType->print( std::cerr ); |
---|
541 | std::cerr << std::endl; |
---|
542 | ) |
---|
543 | if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) { |
---|
544 | PRINT( |
---|
545 | std::cerr << "success!" << std::endl; |
---|
546 | ) |
---|
547 | SymTab::Indexer newDecls( decls ); |
---|
548 | addToIndexer( newHave, newDecls ); |
---|
549 | Alternative newerAlt( newAlt ); |
---|
550 | newerAlt.env = newEnv; |
---|
551 | assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() ); |
---|
552 | |
---|
553 | // everything with an empty idChain was pulled in by the current assertion. |
---|
554 | // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found. |
---|
555 | for ( auto & a : newerNeed ) { |
---|
556 | if ( a.second.idChain.empty() ) { |
---|
557 | a.second.idChain = cur->second.idChain; |
---|
558 | a.second.idChain.push_back( curDecl->get_uniqueId() ); |
---|
559 | } |
---|
560 | } |
---|
561 | |
---|
562 | Expression *varExpr = data.combine( newerAlt.cvtCost ); |
---|
563 | delete varExpr->get_result(); |
---|
564 | varExpr->set_result( adjType->clone() ); |
---|
565 | PRINT( |
---|
566 | std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " "; |
---|
567 | curDecl->print( std::cerr ); |
---|
568 | std::cerr << " with declaration " << candidate->get_uniqueId() << " "; |
---|
569 | candidate->print( std::cerr ); |
---|
570 | std::cerr << std::endl; |
---|
571 | ) |
---|
572 | // follow the current assertion's ID chain to find the correct set of inferred parameters to add the candidate to (i.e. the set of inferred parameters belonging to the entity which requested the assertion parameter). |
---|
573 | InferredParams * inferParameters = &newerAlt.expr->get_inferParams(); |
---|
574 | for ( UniqueId id : cur->second.idChain ) { |
---|
575 | inferParameters = (*inferParameters)[ id ].inferParams.get(); |
---|
576 | } |
---|
577 | // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions |
---|
578 | (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( candidate->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr ); |
---|
579 | inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, level, indexer, out ); |
---|
580 | } else { |
---|
581 | delete adjType; |
---|
582 | } |
---|
583 | } |
---|
584 | } |
---|
585 | |
---|
586 | template< typename OutputIterator > |
---|
587 | void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) { |
---|
588 | // PRINT( |
---|
589 | // std::cerr << "inferParameters: assertions needed are" << std::endl; |
---|
590 | // printAll( need, std::cerr, 8 ); |
---|
591 | // ) |
---|
592 | SymTab::Indexer decls( indexer ); |
---|
593 | // PRINT( |
---|
594 | // std::cerr << "============= original indexer" << std::endl; |
---|
595 | // indexer.print( std::cerr ); |
---|
596 | // std::cerr << "============= new indexer" << std::endl; |
---|
597 | // decls.print( std::cerr ); |
---|
598 | // ) |
---|
599 | addToIndexer( have, decls ); |
---|
600 | AssertionSet newNeed; |
---|
601 | PRINT( |
---|
602 | std::cerr << "env is: " << std::endl; |
---|
603 | newAlt.env.print( std::cerr, 0 ); |
---|
604 | std::cerr << std::endl; |
---|
605 | ) |
---|
606 | |
---|
607 | inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out ); |
---|
608 | // PRINT( |
---|
609 | // std::cerr << "declaration 14 is "; |
---|
610 | // Declaration::declFromId |
---|
611 | // *out++ = newAlt; |
---|
612 | // ) |
---|
613 | } |
---|
614 | |
---|
615 | /// Gets a default value from an initializer, nullptr if not present |
---|
616 | ConstantExpr* getDefaultValue( Initializer* init ) { |
---|
617 | if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) { |
---|
618 | if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->value ) ) { |
---|
619 | return dynamic_cast<ConstantExpr*>( ce->arg ); |
---|
620 | } else { |
---|
621 | return dynamic_cast<ConstantExpr*>( si->value ); |
---|
622 | } |
---|
623 | } |
---|
624 | return nullptr; |
---|
625 | } |
---|
626 | |
---|
627 | /// State to iteratively build a match of parameter expressions to arguments |
---|
628 | struct ArgPack { |
---|
629 | std::size_t parent; ///< Index of parent pack |
---|
630 | std::unique_ptr<Expression> expr; ///< The argument stored here |
---|
631 | Cost cost; ///< The cost of this argument |
---|
632 | TypeEnvironment env; ///< Environment for this pack |
---|
633 | AssertionSet need; ///< Assertions outstanding for this pack |
---|
634 | AssertionSet have; ///< Assertions found for this pack |
---|
635 | OpenVarSet openVars; ///< Open variables for this pack |
---|
636 | unsigned nextArg; ///< Index of next argument in arguments list |
---|
637 | unsigned tupleStart; ///< Number of tuples that start at this index |
---|
638 | unsigned nextExpl; ///< Index of next exploded element |
---|
639 | unsigned explAlt; ///< Index of alternative for nextExpl > 0 |
---|
640 | |
---|
641 | ArgPack() |
---|
642 | : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0), |
---|
643 | tupleStart(0), nextExpl(0), explAlt(0) {} |
---|
644 | |
---|
645 | ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, |
---|
646 | const OpenVarSet& openVars) |
---|
647 | : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have), |
---|
648 | openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {} |
---|
649 | |
---|
650 | ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need, |
---|
651 | AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg, |
---|
652 | unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0, |
---|
653 | unsigned explAlt = 0 ) |
---|
654 | : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)), |
---|
655 | have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart), |
---|
656 | nextExpl(nextExpl), explAlt(explAlt) {} |
---|
657 | |
---|
658 | ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have, |
---|
659 | OpenVarSet&& openVars, unsigned nextArg, Cost added ) |
---|
660 | : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added), |
---|
661 | env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)), |
---|
662 | nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {} |
---|
663 | |
---|
664 | /// true iff this pack is in the middle of an exploded argument |
---|
665 | bool hasExpl() const { return nextExpl > 0; } |
---|
666 | |
---|
667 | /// Gets the list of exploded alternatives for this pack |
---|
668 | const ExplodedActual& getExpl( const ExplodedArgs& args ) const { |
---|
669 | return args[nextArg-1][explAlt]; |
---|
670 | } |
---|
671 | |
---|
672 | /// Ends a tuple expression, consolidating the appropriate actuals |
---|
673 | void endTuple( const std::vector<ArgPack>& packs ) { |
---|
674 | // add all expressions in tuple to list, summing cost |
---|
675 | std::list<Expression*> exprs; |
---|
676 | const ArgPack* pack = this; |
---|
677 | if ( expr ) { exprs.push_front( expr.release() ); } |
---|
678 | while ( pack->tupleStart == 0 ) { |
---|
679 | pack = &packs[pack->parent]; |
---|
680 | exprs.push_front( pack->expr->clone() ); |
---|
681 | cost += pack->cost; |
---|
682 | } |
---|
683 | // reset pack to appropriate tuple |
---|
684 | expr.reset( new TupleExpr( exprs ) ); |
---|
685 | tupleStart = pack->tupleStart - 1; |
---|
686 | parent = pack->parent; |
---|
687 | } |
---|
688 | }; |
---|
689 | |
---|
690 | /// Instantiates an argument to match a formal, returns false if no results left |
---|
691 | bool instantiateArgument( Type* formalType, Initializer* initializer, |
---|
692 | const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart, |
---|
693 | const SymTab::Indexer& indexer, unsigned nTuples = 0 ) { |
---|
694 | if ( TupleType * tupleType = dynamic_cast<TupleType*>( formalType ) ) { |
---|
695 | // formalType is a TupleType - group actuals into a TupleExpr |
---|
696 | ++nTuples; |
---|
697 | for ( Type* type : *tupleType ) { |
---|
698 | // xxx - dropping initializer changes behaviour from previous, but seems correct |
---|
699 | // ^^^ need to handle the case where a tuple has a default argument |
---|
700 | if ( ! instantiateArgument( |
---|
701 | type, nullptr, args, results, genStart, indexer, nTuples ) ) |
---|
702 | return false; |
---|
703 | nTuples = 0; |
---|
704 | } |
---|
705 | // re-consititute tuples for final generation |
---|
706 | for ( auto i = genStart; i < results.size(); ++i ) { |
---|
707 | results[i].endTuple( results ); |
---|
708 | } |
---|
709 | return true; |
---|
710 | } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) { |
---|
711 | // formalType is a ttype, consumes all remaining arguments |
---|
712 | // xxx - mixing default arguments with variadic?? |
---|
713 | |
---|
714 | // completed tuples; will be spliced to end of results to finish |
---|
715 | std::vector<ArgPack> finalResults{}; |
---|
716 | |
---|
717 | // iterate until all results completed |
---|
718 | std::size_t genEnd; |
---|
719 | ++nTuples; |
---|
720 | do { |
---|
721 | genEnd = results.size(); |
---|
722 | |
---|
723 | // add another argument to results |
---|
724 | for ( std::size_t i = genStart; i < genEnd; ++i ) { |
---|
725 | auto nextArg = results[i].nextArg; |
---|
726 | |
---|
727 | // use next element of exploded tuple if present |
---|
728 | if ( results[i].hasExpl() ) { |
---|
729 | const ExplodedActual& expl = results[i].getExpl( args ); |
---|
730 | |
---|
731 | unsigned nextExpl = results[i].nextExpl + 1; |
---|
732 | if ( nextExpl == expl.exprs.size() ) { |
---|
733 | nextExpl = 0; |
---|
734 | } |
---|
735 | |
---|
736 | results.emplace_back( |
---|
737 | i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env), |
---|
738 | copy(results[i].need), copy(results[i].have), |
---|
739 | copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl, |
---|
740 | results[i].explAlt ); |
---|
741 | |
---|
742 | continue; |
---|
743 | } |
---|
744 | |
---|
745 | // finish result when out of arguments |
---|
746 | if ( nextArg >= args.size() ) { |
---|
747 | ArgPack newResult{ |
---|
748 | results[i].env, results[i].need, results[i].have, |
---|
749 | results[i].openVars }; |
---|
750 | newResult.nextArg = nextArg; |
---|
751 | Type* argType; |
---|
752 | |
---|
753 | if ( nTuples > 0 || ! results[i].expr ) { |
---|
754 | // first iteration or no expression to clone, |
---|
755 | // push empty tuple expression |
---|
756 | newResult.parent = i; |
---|
757 | std::list<Expression*> emptyList; |
---|
758 | newResult.expr.reset( new TupleExpr( emptyList ) ); |
---|
759 | argType = newResult.expr->get_result(); |
---|
760 | } else { |
---|
761 | // clone result to collect tuple |
---|
762 | newResult.parent = results[i].parent; |
---|
763 | newResult.cost = results[i].cost; |
---|
764 | newResult.tupleStart = results[i].tupleStart; |
---|
765 | newResult.expr.reset( results[i].expr->clone() ); |
---|
766 | argType = newResult.expr->get_result(); |
---|
767 | |
---|
768 | if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) { |
---|
769 | // the case where a ttype value is passed directly is special, |
---|
770 | // e.g. for argument forwarding purposes |
---|
771 | // xxx - what if passing multiple arguments, last of which is |
---|
772 | // ttype? |
---|
773 | // xxx - what would happen if unify was changed so that unifying |
---|
774 | // tuple |
---|
775 | // types flattened both before unifying lists? then pass in |
---|
776 | // TupleType (ttype) below. |
---|
777 | --newResult.tupleStart; |
---|
778 | } else { |
---|
779 | // collapse leftover arguments into tuple |
---|
780 | newResult.endTuple( results ); |
---|
781 | argType = newResult.expr->get_result(); |
---|
782 | } |
---|
783 | } |
---|
784 | |
---|
785 | // check unification for ttype before adding to final |
---|
786 | if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have, |
---|
787 | newResult.openVars, indexer ) ) { |
---|
788 | finalResults.push_back( move(newResult) ); |
---|
789 | } |
---|
790 | |
---|
791 | continue; |
---|
792 | } |
---|
793 | |
---|
794 | // add each possible next argument |
---|
795 | for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { |
---|
796 | const ExplodedActual& expl = args[nextArg][j]; |
---|
797 | |
---|
798 | // fresh copies of parent parameters for this iteration |
---|
799 | TypeEnvironment env = results[i].env; |
---|
800 | OpenVarSet openVars = results[i].openVars; |
---|
801 | |
---|
802 | env.addActual( expl.env, openVars ); |
---|
803 | |
---|
804 | // skip empty tuple arguments by (near-)cloning parent into next gen |
---|
805 | if ( expl.exprs.empty() ) { |
---|
806 | results.emplace_back( |
---|
807 | results[i], move(env), copy(results[i].need), |
---|
808 | copy(results[i].have), move(openVars), nextArg + 1, expl.cost ); |
---|
809 | |
---|
810 | continue; |
---|
811 | } |
---|
812 | |
---|
813 | // add new result |
---|
814 | results.emplace_back( |
---|
815 | i, expl.exprs.front().get(), move(env), copy(results[i].need), |
---|
816 | copy(results[i].have), move(openVars), nextArg + 1, |
---|
817 | nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); |
---|
818 | } |
---|
819 | } |
---|
820 | |
---|
821 | // reset for next round |
---|
822 | genStart = genEnd; |
---|
823 | nTuples = 0; |
---|
824 | } while ( genEnd != results.size() ); |
---|
825 | |
---|
826 | // splice final results onto results |
---|
827 | for ( std::size_t i = 0; i < finalResults.size(); ++i ) { |
---|
828 | results.push_back( move(finalResults[i]) ); |
---|
829 | } |
---|
830 | return ! finalResults.empty(); |
---|
831 | } |
---|
832 | |
---|
833 | // iterate each current subresult |
---|
834 | std::size_t genEnd = results.size(); |
---|
835 | for ( std::size_t i = genStart; i < genEnd; ++i ) { |
---|
836 | auto nextArg = results[i].nextArg; |
---|
837 | |
---|
838 | // use remainder of exploded tuple if present |
---|
839 | if ( results[i].hasExpl() ) { |
---|
840 | const ExplodedActual& expl = results[i].getExpl( args ); |
---|
841 | Expression* expr = expl.exprs[results[i].nextExpl].get(); |
---|
842 | |
---|
843 | TypeEnvironment env = results[i].env; |
---|
844 | AssertionSet need = results[i].need, have = results[i].have; |
---|
845 | OpenVarSet openVars = results[i].openVars; |
---|
846 | |
---|
847 | Type* actualType = expr->get_result(); |
---|
848 | |
---|
849 | PRINT( |
---|
850 | std::cerr << "formal type is "; |
---|
851 | formalType->print( std::cerr ); |
---|
852 | std::cerr << std::endl << "actual type is "; |
---|
853 | actualType->print( std::cerr ); |
---|
854 | std::cerr << std::endl; |
---|
855 | ) |
---|
856 | |
---|
857 | if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { |
---|
858 | unsigned nextExpl = results[i].nextExpl + 1; |
---|
859 | if ( nextExpl == expl.exprs.size() ) { |
---|
860 | nextExpl = 0; |
---|
861 | } |
---|
862 | |
---|
863 | results.emplace_back( |
---|
864 | i, expr, move(env), move(need), move(have), move(openVars), nextArg, |
---|
865 | nTuples, Cost::zero, nextExpl, results[i].explAlt ); |
---|
866 | } |
---|
867 | |
---|
868 | continue; |
---|
869 | } |
---|
870 | |
---|
871 | // use default initializers if out of arguments |
---|
872 | if ( nextArg >= args.size() ) { |
---|
873 | if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { |
---|
874 | if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) { |
---|
875 | TypeEnvironment env = results[i].env; |
---|
876 | AssertionSet need = results[i].need, have = results[i].have; |
---|
877 | OpenVarSet openVars = results[i].openVars; |
---|
878 | |
---|
879 | if ( unify( formalType, cnst->get_type(), env, need, have, openVars, |
---|
880 | indexer ) ) { |
---|
881 | results.emplace_back( |
---|
882 | i, new DefaultArgExpr( cnstExpr ), move(env), move(need), move(have), |
---|
883 | move(openVars), nextArg, nTuples ); |
---|
884 | } |
---|
885 | } |
---|
886 | } |
---|
887 | |
---|
888 | continue; |
---|
889 | } |
---|
890 | |
---|
891 | // Check each possible next argument |
---|
892 | for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { |
---|
893 | const ExplodedActual& expl = args[nextArg][j]; |
---|
894 | |
---|
895 | // fresh copies of parent parameters for this iteration |
---|
896 | TypeEnvironment env = results[i].env; |
---|
897 | AssertionSet need = results[i].need, have = results[i].have; |
---|
898 | OpenVarSet openVars = results[i].openVars; |
---|
899 | |
---|
900 | env.addActual( expl.env, openVars ); |
---|
901 | |
---|
902 | // skip empty tuple arguments by (near-)cloning parent into next gen |
---|
903 | if ( expl.exprs.empty() ) { |
---|
904 | results.emplace_back( |
---|
905 | results[i], move(env), move(need), move(have), move(openVars), |
---|
906 | nextArg + 1, expl.cost ); |
---|
907 | |
---|
908 | continue; |
---|
909 | } |
---|
910 | |
---|
911 | // consider only first exploded actual |
---|
912 | Expression* expr = expl.exprs.front().get(); |
---|
913 | Type* actualType = expr->result->clone(); |
---|
914 | |
---|
915 | PRINT( |
---|
916 | std::cerr << "formal type is "; |
---|
917 | formalType->print( std::cerr ); |
---|
918 | std::cerr << std::endl << "actual type is "; |
---|
919 | actualType->print( std::cerr ); |
---|
920 | std::cerr << std::endl; |
---|
921 | ) |
---|
922 | |
---|
923 | // attempt to unify types |
---|
924 | if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { |
---|
925 | // add new result |
---|
926 | results.emplace_back( |
---|
927 | i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1, |
---|
928 | nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); |
---|
929 | } |
---|
930 | } |
---|
931 | } |
---|
932 | |
---|
933 | // reset for next parameter |
---|
934 | genStart = genEnd; |
---|
935 | |
---|
936 | return genEnd != results.size(); |
---|
937 | } |
---|
938 | |
---|
939 | template<typename OutputIterator> |
---|
940 | void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, ArgPack& result, |
---|
941 | const std::vector<ArgPack>& results, OutputIterator out ) { |
---|
942 | ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); |
---|
943 | // sum cost and accumulate actuals |
---|
944 | std::list<Expression*>& args = appExpr->args; |
---|
945 | Cost cost = func.cost; |
---|
946 | const ArgPack* pack = &result; |
---|
947 | while ( pack->expr ) { |
---|
948 | args.push_front( pack->expr->clone() ); |
---|
949 | cost += pack->cost; |
---|
950 | pack = &results[pack->parent]; |
---|
951 | } |
---|
952 | // build and validate new alternative |
---|
953 | Alternative newAlt( appExpr, result.env, cost ); |
---|
954 | PRINT( |
---|
955 | std::cerr << "instantiate function success: " << appExpr << std::endl; |
---|
956 | std::cerr << "need assertions:" << std::endl; |
---|
957 | printAssertionSet( result.need, std::cerr, 8 ); |
---|
958 | ) |
---|
959 | inferParameters( result.need, result.have, newAlt, result.openVars, out ); |
---|
960 | } |
---|
961 | |
---|
962 | template<typename OutputIterator> |
---|
963 | void AlternativeFinder::Finder::makeFunctionAlternatives( const Alternative &func, |
---|
964 | FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) { |
---|
965 | OpenVarSet funcOpenVars; |
---|
966 | AssertionSet funcNeed, funcHave; |
---|
967 | TypeEnvironment funcEnv( func.env ); |
---|
968 | makeUnifiableVars( funcType, funcOpenVars, funcNeed ); |
---|
969 | // add all type variables as open variables now so that those not used in the parameter |
---|
970 | // list are still considered open. |
---|
971 | funcEnv.add( funcType->forall ); |
---|
972 | |
---|
973 | if ( targetType && ! targetType->isVoid() && ! funcType->returnVals.empty() ) { |
---|
974 | // attempt to narrow based on expected target type |
---|
975 | Type * returnType = funcType->returnVals.front()->get_type(); |
---|
976 | if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars, |
---|
977 | indexer ) ) { |
---|
978 | // unification failed, don't pursue this function alternative |
---|
979 | return; |
---|
980 | } |
---|
981 | } |
---|
982 | |
---|
983 | // iteratively build matches, one parameter at a time |
---|
984 | std::vector<ArgPack> results; |
---|
985 | results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } ); |
---|
986 | std::size_t genStart = 0; |
---|
987 | |
---|
988 | for ( DeclarationWithType* formal : funcType->parameters ) { |
---|
989 | ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal ); |
---|
990 | if ( ! instantiateArgument( |
---|
991 | obj->type, obj->init, args, results, genStart, indexer ) ) |
---|
992 | return; |
---|
993 | } |
---|
994 | |
---|
995 | if ( funcType->get_isVarArgs() ) { |
---|
996 | // append any unused arguments to vararg pack |
---|
997 | std::size_t genEnd; |
---|
998 | do { |
---|
999 | genEnd = results.size(); |
---|
1000 | |
---|
1001 | // iterate results |
---|
1002 | for ( std::size_t i = genStart; i < genEnd; ++i ) { |
---|
1003 | auto nextArg = results[i].nextArg; |
---|
1004 | |
---|
1005 | // use remainder of exploded tuple if present |
---|
1006 | if ( results[i].hasExpl() ) { |
---|
1007 | const ExplodedActual& expl = results[i].getExpl( args ); |
---|
1008 | |
---|
1009 | unsigned nextExpl = results[i].nextExpl + 1; |
---|
1010 | if ( nextExpl == expl.exprs.size() ) { |
---|
1011 | nextExpl = 0; |
---|
1012 | } |
---|
1013 | |
---|
1014 | results.emplace_back( |
---|
1015 | i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env), |
---|
1016 | copy(results[i].need), copy(results[i].have), |
---|
1017 | copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl, |
---|
1018 | results[i].explAlt ); |
---|
1019 | |
---|
1020 | continue; |
---|
1021 | } |
---|
1022 | |
---|
1023 | // finish result when out of arguments |
---|
1024 | if ( nextArg >= args.size() ) { |
---|
1025 | validateFunctionAlternative( func, results[i], results, out ); |
---|
1026 | |
---|
1027 | continue; |
---|
1028 | } |
---|
1029 | |
---|
1030 | // add each possible next argument |
---|
1031 | for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { |
---|
1032 | const ExplodedActual& expl = args[nextArg][j]; |
---|
1033 | |
---|
1034 | // fresh copies of parent parameters for this iteration |
---|
1035 | TypeEnvironment env = results[i].env; |
---|
1036 | OpenVarSet openVars = results[i].openVars; |
---|
1037 | |
---|
1038 | env.addActual( expl.env, openVars ); |
---|
1039 | |
---|
1040 | // skip empty tuple arguments by (near-)cloning parent into next gen |
---|
1041 | if ( expl.exprs.empty() ) { |
---|
1042 | results.emplace_back( |
---|
1043 | results[i], move(env), copy(results[i].need), |
---|
1044 | copy(results[i].have), move(openVars), nextArg + 1, expl.cost ); |
---|
1045 | |
---|
1046 | continue; |
---|
1047 | } |
---|
1048 | |
---|
1049 | // add new result |
---|
1050 | results.emplace_back( |
---|
1051 | i, expl.exprs.front().get(), move(env), copy(results[i].need), |
---|
1052 | copy(results[i].have), move(openVars), nextArg + 1, 0, |
---|
1053 | expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); |
---|
1054 | } |
---|
1055 | } |
---|
1056 | |
---|
1057 | genStart = genEnd; |
---|
1058 | } while ( genEnd != results.size() ); |
---|
1059 | } else { |
---|
1060 | // filter out results that don't use all the arguments |
---|
1061 | for ( std::size_t i = genStart; i < results.size(); ++i ) { |
---|
1062 | ArgPack& result = results[i]; |
---|
1063 | if ( ! result.hasExpl() && result.nextArg >= args.size() ) { |
---|
1064 | validateFunctionAlternative( func, result, results, out ); |
---|
1065 | } |
---|
1066 | } |
---|
1067 | } |
---|
1068 | } |
---|
1069 | |
---|
1070 | void AlternativeFinder::Finder::postvisit( UntypedExpr *untypedExpr ) { |
---|
1071 | AlternativeFinder funcFinder( indexer, env ); |
---|
1072 | funcFinder.findWithAdjustment( untypedExpr->function ); |
---|
1073 | // if there are no function alternatives, then proceeding is a waste of time. |
---|
1074 | // xxx - findWithAdjustment throws, so this check and others like it shouldn't be necessary. |
---|
1075 | if ( funcFinder.alternatives.empty() ) return; |
---|
1076 | |
---|
1077 | std::vector< AlternativeFinder > argAlternatives; |
---|
1078 | altFinder.findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), |
---|
1079 | back_inserter( argAlternatives ) ); |
---|
1080 | |
---|
1081 | // take care of possible tuple assignments |
---|
1082 | // if not tuple assignment, assignment is taken care of as a normal function call |
---|
1083 | Tuples::handleTupleAssignment( altFinder, untypedExpr, argAlternatives ); |
---|
1084 | |
---|
1085 | // find function operators |
---|
1086 | static NameExpr *opExpr = new NameExpr( "?()" ); |
---|
1087 | AlternativeFinder funcOpFinder( indexer, env ); |
---|
1088 | // it's ok if there aren't any defined function ops |
---|
1089 | funcOpFinder.maybeFind( opExpr ); |
---|
1090 | PRINT( |
---|
1091 | std::cerr << "known function ops:" << std::endl; |
---|
1092 | printAlts( funcOpFinder.alternatives, std::cerr, 1 ); |
---|
1093 | ) |
---|
1094 | |
---|
1095 | // pre-explode arguments |
---|
1096 | ExplodedArgs argExpansions; |
---|
1097 | argExpansions.reserve( argAlternatives.size() ); |
---|
1098 | |
---|
1099 | for ( const AlternativeFinder& arg : argAlternatives ) { |
---|
1100 | argExpansions.emplace_back(); |
---|
1101 | auto& argE = argExpansions.back(); |
---|
1102 | // argE.reserve( arg.alternatives.size() ); |
---|
1103 | |
---|
1104 | for ( const Alternative& actual : arg ) { |
---|
1105 | argE.emplace_back( actual, indexer ); |
---|
1106 | } |
---|
1107 | } |
---|
1108 | |
---|
1109 | AltList candidates; |
---|
1110 | SemanticErrorException errors; |
---|
1111 | for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) { |
---|
1112 | try { |
---|
1113 | PRINT( |
---|
1114 | std::cerr << "working on alternative: " << std::endl; |
---|
1115 | func->print( std::cerr, 8 ); |
---|
1116 | ) |
---|
1117 | // check if the type is pointer to function |
---|
1118 | if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->result->stripReferences() ) ) { |
---|
1119 | if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->base ) ) { |
---|
1120 | Alternative newFunc( *func ); |
---|
1121 | referenceToRvalueConversion( newFunc.expr, newFunc.cost ); |
---|
1122 | makeFunctionAlternatives( newFunc, function, argExpansions, |
---|
1123 | std::back_inserter( candidates ) ); |
---|
1124 | } |
---|
1125 | } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->result->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer) |
---|
1126 | if ( const EqvClass *eqvClass = func->env.lookup( typeInst->name ) ) { |
---|
1127 | if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass->type ) ) { |
---|
1128 | Alternative newFunc( *func ); |
---|
1129 | referenceToRvalueConversion( newFunc.expr, newFunc.cost ); |
---|
1130 | makeFunctionAlternatives( newFunc, function, argExpansions, |
---|
1131 | std::back_inserter( candidates ) ); |
---|
1132 | } // if |
---|
1133 | } // if |
---|
1134 | } |
---|
1135 | } catch ( SemanticErrorException &e ) { |
---|
1136 | errors.append( e ); |
---|
1137 | } |
---|
1138 | } // for |
---|
1139 | |
---|
1140 | // try each function operator ?() with each function alternative |
---|
1141 | if ( ! funcOpFinder.alternatives.empty() ) { |
---|
1142 | // add exploded function alternatives to front of argument list |
---|
1143 | std::vector<ExplodedActual> funcE; |
---|
1144 | funcE.reserve( funcFinder.alternatives.size() ); |
---|
1145 | for ( const Alternative& actual : funcFinder ) { |
---|
1146 | funcE.emplace_back( actual, indexer ); |
---|
1147 | } |
---|
1148 | argExpansions.insert( argExpansions.begin(), move(funcE) ); |
---|
1149 | |
---|
1150 | for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); |
---|
1151 | funcOp != funcOpFinder.alternatives.end(); ++funcOp ) { |
---|
1152 | try { |
---|
1153 | // check if type is a pointer to function |
---|
1154 | if ( PointerType* pointer = dynamic_cast<PointerType*>( |
---|
1155 | funcOp->expr->result->stripReferences() ) ) { |
---|
1156 | if ( FunctionType* function = |
---|
1157 | dynamic_cast<FunctionType*>( pointer->base ) ) { |
---|
1158 | Alternative newFunc( *funcOp ); |
---|
1159 | referenceToRvalueConversion( newFunc.expr, newFunc.cost ); |
---|
1160 | makeFunctionAlternatives( newFunc, function, argExpansions, |
---|
1161 | std::back_inserter( candidates ) ); |
---|
1162 | } |
---|
1163 | } |
---|
1164 | } catch ( SemanticErrorException &e ) { |
---|
1165 | errors.append( e ); |
---|
1166 | } |
---|
1167 | } |
---|
1168 | } |
---|
1169 | |
---|
1170 | // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions |
---|
1171 | if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; } |
---|
1172 | |
---|
1173 | // compute conversionsion costs |
---|
1174 | for ( Alternative& withFunc : candidates ) { |
---|
1175 | Cost cvtCost = computeApplicationConversionCost( withFunc, indexer ); |
---|
1176 | |
---|
1177 | PRINT( |
---|
1178 | ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr ); |
---|
1179 | PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->function->result ); |
---|
1180 | FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->base ); |
---|
1181 | std::cerr << "Case +++++++++++++ " << appExpr->function << std::endl; |
---|
1182 | std::cerr << "formals are:" << std::endl; |
---|
1183 | printAll( function->parameters, std::cerr, 8 ); |
---|
1184 | std::cerr << "actuals are:" << std::endl; |
---|
1185 | printAll( appExpr->args, std::cerr, 8 ); |
---|
1186 | std::cerr << "bindings are:" << std::endl; |
---|
1187 | withFunc.env.print( std::cerr, 8 ); |
---|
1188 | std::cerr << "cost is: " << withFunc.cost << std::endl; |
---|
1189 | std::cerr << "cost of conversion is:" << cvtCost << std::endl; |
---|
1190 | ) |
---|
1191 | if ( cvtCost != Cost::infinity ) { |
---|
1192 | withFunc.cvtCost = cvtCost; |
---|
1193 | alternatives.push_back( withFunc ); |
---|
1194 | } // if |
---|
1195 | } // for |
---|
1196 | |
---|
1197 | candidates = move(alternatives); |
---|
1198 | |
---|
1199 | // use a new list so that alternatives are not examined by addAnonConversions twice. |
---|
1200 | AltList winners; |
---|
1201 | findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) ); |
---|
1202 | |
---|
1203 | // function may return struct or union value, in which case we need to add alternatives |
---|
1204 | // for implicitconversions to each of the anonymous members, must happen after findMinCost |
---|
1205 | // since anon conversions are never the cheapest expression |
---|
1206 | for ( const Alternative & alt : winners ) { |
---|
1207 | addAnonConversions( alt ); |
---|
1208 | } |
---|
1209 | spliceBegin( alternatives, winners ); |
---|
1210 | |
---|
1211 | if ( alternatives.empty() && targetType && ! targetType->isVoid() ) { |
---|
1212 | // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a |
---|
1213 | // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example, |
---|
1214 | // forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t ); |
---|
1215 | // const char * x = "hello world"; |
---|
1216 | // unsigned char ch = x[0]; |
---|
1217 | // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified |
---|
1218 | // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should |
---|
1219 | // fix this issue in a more robust way. |
---|
1220 | targetType = nullptr; |
---|
1221 | postvisit( untypedExpr ); |
---|
1222 | } |
---|
1223 | } |
---|
1224 | |
---|
1225 | bool isLvalue( Expression *expr ) { |
---|
1226 | // xxx - recurse into tuples? |
---|
1227 | return expr->result && ( expr->result->get_lvalue() || dynamic_cast< ReferenceType * >( expr->result ) ); |
---|
1228 | } |
---|
1229 | |
---|
1230 | void AlternativeFinder::Finder::postvisit( AddressExpr *addressExpr ) { |
---|
1231 | AlternativeFinder finder( indexer, env ); |
---|
1232 | finder.find( addressExpr->get_arg() ); |
---|
1233 | for ( Alternative& alt : finder.alternatives ) { |
---|
1234 | if ( isLvalue( alt.expr ) ) { |
---|
1235 | alternatives.push_back( |
---|
1236 | Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } ); |
---|
1237 | } // if |
---|
1238 | } // for |
---|
1239 | } |
---|
1240 | |
---|
1241 | void AlternativeFinder::Finder::postvisit( LabelAddressExpr * expr ) { |
---|
1242 | alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } ); |
---|
1243 | } |
---|
1244 | |
---|
1245 | Expression * restructureCast( Expression * argExpr, Type * toType, bool isGenerated ) { |
---|
1246 | if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) { |
---|
1247 | // Argument expression is a tuple and the target type is not void and not a reference type. |
---|
1248 | // Cast each member of the tuple to its corresponding target type, producing the tuple of those |
---|
1249 | // cast expressions. If there are more components of the tuple than components in the target type, |
---|
1250 | // then excess components do not come out in the result expression (but UniqueExprs ensure that |
---|
1251 | // side effects will still be done). |
---|
1252 | if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) { |
---|
1253 | // expressions which may contain side effects require a single unique instance of the expression. |
---|
1254 | argExpr = new UniqueExpr( argExpr ); |
---|
1255 | } |
---|
1256 | std::list< Expression * > componentExprs; |
---|
1257 | for ( unsigned int i = 0; i < toType->size(); i++ ) { |
---|
1258 | // cast each component |
---|
1259 | TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i ); |
---|
1260 | componentExprs.push_back( restructureCast( idx, toType->getComponent( i ), isGenerated ) ); |
---|
1261 | } |
---|
1262 | delete argExpr; |
---|
1263 | assert( componentExprs.size() > 0 ); |
---|
1264 | // produce the tuple of casts |
---|
1265 | return new TupleExpr( componentExprs ); |
---|
1266 | } else { |
---|
1267 | // handle normally |
---|
1268 | CastExpr * ret = new CastExpr( argExpr, toType->clone() ); |
---|
1269 | ret->isGenerated = isGenerated; |
---|
1270 | return ret; |
---|
1271 | } |
---|
1272 | } |
---|
1273 | |
---|
1274 | void AlternativeFinder::Finder::postvisit( CastExpr *castExpr ) { |
---|
1275 | Type *& toType = castExpr->get_result(); |
---|
1276 | assert( toType ); |
---|
1277 | toType = resolveTypeof( toType, indexer ); |
---|
1278 | SymTab::validateType( toType, &indexer ); |
---|
1279 | adjustExprType( toType, env, indexer ); |
---|
1280 | |
---|
1281 | AlternativeFinder finder( indexer, env ); |
---|
1282 | finder.targetType = toType; |
---|
1283 | finder.findWithAdjustment( castExpr->arg ); |
---|
1284 | |
---|
1285 | AltList candidates; |
---|
1286 | for ( Alternative & alt : finder.alternatives ) { |
---|
1287 | AssertionSet needAssertions, haveAssertions; |
---|
1288 | OpenVarSet openVars; |
---|
1289 | |
---|
1290 | alt.env.extractOpenVars( openVars ); |
---|
1291 | |
---|
1292 | // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a |
---|
1293 | // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results |
---|
1294 | // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast |
---|
1295 | // to. |
---|
1296 | int discardedValues = alt.expr->result->size() - castExpr->result->size(); |
---|
1297 | if ( discardedValues < 0 ) continue; |
---|
1298 | // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not |
---|
1299 | // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3])) |
---|
1300 | // unification run for side-effects |
---|
1301 | unify( castExpr->result, alt.expr->result, alt.env, needAssertions, |
---|
1302 | haveAssertions, openVars, indexer ); |
---|
1303 | Cost thisCost = castCost( alt.expr->result, castExpr->result, indexer, |
---|
1304 | alt.env ); |
---|
1305 | PRINT( |
---|
1306 | std::cerr << "working on cast with result: " << castExpr->result << std::endl; |
---|
1307 | std::cerr << "and expr type: " << alt.expr->result << std::endl; |
---|
1308 | std::cerr << "env: " << alt.env << std::endl; |
---|
1309 | ) |
---|
1310 | if ( thisCost != Cost::infinity ) { |
---|
1311 | PRINT( |
---|
1312 | std::cerr << "has finite cost." << std::endl; |
---|
1313 | ) |
---|
1314 | // count one safe conversion for each value that is thrown away |
---|
1315 | thisCost.incSafe( discardedValues ); |
---|
1316 | Alternative newAlt( restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), alt.env, |
---|
1317 | alt.cost, thisCost ); |
---|
1318 | inferParameters( needAssertions, haveAssertions, newAlt, openVars, |
---|
1319 | back_inserter( candidates ) ); |
---|
1320 | } // if |
---|
1321 | } // for |
---|
1322 | |
---|
1323 | // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the |
---|
1324 | // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice |
---|
1325 | // selects first based on argument cost, then on conversion cost. |
---|
1326 | AltList minArgCost; |
---|
1327 | findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) ); |
---|
1328 | findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) ); |
---|
1329 | } |
---|
1330 | |
---|
1331 | void AlternativeFinder::Finder::postvisit( VirtualCastExpr * castExpr ) { |
---|
1332 | assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." ); |
---|
1333 | AlternativeFinder finder( indexer, env ); |
---|
1334 | // don't prune here, since it's guaranteed all alternatives will have the same type |
---|
1335 | finder.findWithoutPrune( castExpr->get_arg() ); |
---|
1336 | for ( Alternative & alt : finder.alternatives ) { |
---|
1337 | alternatives.push_back( Alternative( |
---|
1338 | new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ), |
---|
1339 | alt.env, alt.cost ) ); |
---|
1340 | } |
---|
1341 | } |
---|
1342 | |
---|
1343 | namespace { |
---|
1344 | /// Gets name from untyped member expression (member must be NameExpr) |
---|
1345 | const std::string& get_member_name( UntypedMemberExpr *memberExpr ) { |
---|
1346 | NameExpr * nameExpr = dynamic_cast< NameExpr * >( memberExpr->get_member() ); |
---|
1347 | assert( nameExpr ); |
---|
1348 | return nameExpr->get_name(); |
---|
1349 | } |
---|
1350 | } |
---|
1351 | |
---|
1352 | void AlternativeFinder::Finder::postvisit( UntypedMemberExpr *memberExpr ) { |
---|
1353 | AlternativeFinder funcFinder( indexer, env ); |
---|
1354 | funcFinder.findWithAdjustment( memberExpr->get_aggregate() ); |
---|
1355 | for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) { |
---|
1356 | // it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value |
---|
1357 | Cost cost = agg->cost; |
---|
1358 | Expression * aggrExpr = agg->expr->clone(); |
---|
1359 | referenceToRvalueConversion( aggrExpr, cost ); |
---|
1360 | std::unique_ptr<Expression> guard( aggrExpr ); |
---|
1361 | |
---|
1362 | // find member of the given type |
---|
1363 | if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) { |
---|
1364 | addAggMembers( structInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) ); |
---|
1365 | } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) { |
---|
1366 | addAggMembers( unionInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) ); |
---|
1367 | } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) { |
---|
1368 | addTupleMembers( tupleType, aggrExpr, cost, agg->env, memberExpr->get_member() ); |
---|
1369 | } // if |
---|
1370 | } // for |
---|
1371 | } |
---|
1372 | |
---|
1373 | void AlternativeFinder::Finder::postvisit( MemberExpr *memberExpr ) { |
---|
1374 | alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) ); |
---|
1375 | } |
---|
1376 | |
---|
1377 | void AlternativeFinder::Finder::postvisit( NameExpr *nameExpr ) { |
---|
1378 | std::list< SymTab::Indexer::IdData > declList; |
---|
1379 | indexer.lookupId( nameExpr->name, declList ); |
---|
1380 | PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; ) |
---|
1381 | for ( auto & data : declList ) { |
---|
1382 | Cost cost = Cost::zero; |
---|
1383 | Expression * newExpr = data.combine( cost ); |
---|
1384 | |
---|
1385 | // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so |
---|
1386 | // can't construct in place and use vector::back |
---|
1387 | Alternative newAlt( newExpr, env, Cost::zero, cost ); |
---|
1388 | PRINT( |
---|
1389 | std::cerr << "decl is "; |
---|
1390 | data.id->print( std::cerr ); |
---|
1391 | std::cerr << std::endl; |
---|
1392 | std::cerr << "newExpr is "; |
---|
1393 | newExpr->print( std::cerr ); |
---|
1394 | std::cerr << std::endl; |
---|
1395 | ) |
---|
1396 | renameTypes( newAlt.expr ); |
---|
1397 | addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression. |
---|
1398 | alternatives.push_back( std::move(newAlt) ); |
---|
1399 | } // for |
---|
1400 | } |
---|
1401 | |
---|
1402 | void AlternativeFinder::Finder::postvisit( VariableExpr *variableExpr ) { |
---|
1403 | // not sufficient to clone here, because variable's type may have changed |
---|
1404 | // since the VariableExpr was originally created. |
---|
1405 | alternatives.push_back( Alternative( new VariableExpr( variableExpr->var ), env, Cost::zero ) ); |
---|
1406 | } |
---|
1407 | |
---|
1408 | void AlternativeFinder::Finder::postvisit( ConstantExpr *constantExpr ) { |
---|
1409 | alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) ); |
---|
1410 | } |
---|
1411 | |
---|
1412 | void AlternativeFinder::Finder::postvisit( SizeofExpr *sizeofExpr ) { |
---|
1413 | if ( sizeofExpr->get_isType() ) { |
---|
1414 | Type * newType = sizeofExpr->get_type()->clone(); |
---|
1415 | alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) ); |
---|
1416 | } else { |
---|
1417 | // find all alternatives for the argument to sizeof |
---|
1418 | AlternativeFinder finder( indexer, env ); |
---|
1419 | finder.find( sizeofExpr->get_expr() ); |
---|
1420 | // find the lowest cost alternative among the alternatives, otherwise ambiguous |
---|
1421 | AltList winners; |
---|
1422 | findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) ); |
---|
1423 | if ( winners.size() != 1 ) { |
---|
1424 | SemanticError( sizeofExpr->get_expr(), "Ambiguous expression in sizeof operand: " ); |
---|
1425 | } // if |
---|
1426 | // return the lowest cost alternative for the argument |
---|
1427 | Alternative &choice = winners.front(); |
---|
1428 | referenceToRvalueConversion( choice.expr, choice.cost ); |
---|
1429 | alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) ); |
---|
1430 | } // if |
---|
1431 | } |
---|
1432 | |
---|
1433 | void AlternativeFinder::Finder::postvisit( AlignofExpr *alignofExpr ) { |
---|
1434 | if ( alignofExpr->get_isType() ) { |
---|
1435 | Type * newType = alignofExpr->get_type()->clone(); |
---|
1436 | alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) ); |
---|
1437 | } else { |
---|
1438 | // find all alternatives for the argument to sizeof |
---|
1439 | AlternativeFinder finder( indexer, env ); |
---|
1440 | finder.find( alignofExpr->get_expr() ); |
---|
1441 | // find the lowest cost alternative among the alternatives, otherwise ambiguous |
---|
1442 | AltList winners; |
---|
1443 | findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) ); |
---|
1444 | if ( winners.size() != 1 ) { |
---|
1445 | SemanticError( alignofExpr->get_expr(), "Ambiguous expression in alignof operand: " ); |
---|
1446 | } // if |
---|
1447 | // return the lowest cost alternative for the argument |
---|
1448 | Alternative &choice = winners.front(); |
---|
1449 | referenceToRvalueConversion( choice.expr, choice.cost ); |
---|
1450 | alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) ); |
---|
1451 | } // if |
---|
1452 | } |
---|
1453 | |
---|
1454 | template< typename StructOrUnionType > |
---|
1455 | void AlternativeFinder::Finder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) { |
---|
1456 | std::list< Declaration* > members; |
---|
1457 | aggInst->lookup( name, members ); |
---|
1458 | for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) { |
---|
1459 | if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) { |
---|
1460 | alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) ); |
---|
1461 | renameTypes( alternatives.back().expr ); |
---|
1462 | } else { |
---|
1463 | assert( false ); |
---|
1464 | } |
---|
1465 | } |
---|
1466 | } |
---|
1467 | |
---|
1468 | void AlternativeFinder::Finder::postvisit( UntypedOffsetofExpr *offsetofExpr ) { |
---|
1469 | AlternativeFinder funcFinder( indexer, env ); |
---|
1470 | // xxx - resolveTypeof? |
---|
1471 | if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) { |
---|
1472 | addOffsetof( structInst, offsetofExpr->member ); |
---|
1473 | } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) { |
---|
1474 | addOffsetof( unionInst, offsetofExpr->member ); |
---|
1475 | } |
---|
1476 | } |
---|
1477 | |
---|
1478 | void AlternativeFinder::Finder::postvisit( OffsetofExpr *offsetofExpr ) { |
---|
1479 | alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) ); |
---|
1480 | } |
---|
1481 | |
---|
1482 | void AlternativeFinder::Finder::postvisit( OffsetPackExpr *offsetPackExpr ) { |
---|
1483 | alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) ); |
---|
1484 | } |
---|
1485 | |
---|
1486 | namespace { |
---|
1487 | void resolveAttr( SymTab::Indexer::IdData data, FunctionType *function, Type *argType, const TypeEnvironment &env, AlternativeFinder & finder ) { |
---|
1488 | // assume no polymorphism |
---|
1489 | // assume no implicit conversions |
---|
1490 | assert( function->get_parameters().size() == 1 ); |
---|
1491 | PRINT( |
---|
1492 | std::cerr << "resolvAttr: funcDecl is "; |
---|
1493 | data.id->print( std::cerr ); |
---|
1494 | std::cerr << " argType is "; |
---|
1495 | argType->print( std::cerr ); |
---|
1496 | std::cerr << std::endl; |
---|
1497 | ) |
---|
1498 | const SymTab::Indexer & indexer = finder.get_indexer(); |
---|
1499 | AltList & alternatives = finder.get_alternatives(); |
---|
1500 | if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) { |
---|
1501 | Cost cost = Cost::zero; |
---|
1502 | Expression * newExpr = data.combine( cost ); |
---|
1503 | alternatives.push_back( Alternative( new AttrExpr( newExpr, argType->clone() ), env, Cost::zero, cost ) ); |
---|
1504 | for ( DeclarationWithType * retVal : function->returnVals ) { |
---|
1505 | alternatives.back().expr->result = retVal->get_type()->clone(); |
---|
1506 | } // for |
---|
1507 | } // if |
---|
1508 | } |
---|
1509 | } |
---|
1510 | |
---|
1511 | void AlternativeFinder::Finder::postvisit( AttrExpr *attrExpr ) { |
---|
1512 | // assume no 'pointer-to-attribute' |
---|
1513 | NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() ); |
---|
1514 | assert( nameExpr ); |
---|
1515 | std::list< SymTab::Indexer::IdData > attrList; |
---|
1516 | indexer.lookupId( nameExpr->get_name(), attrList ); |
---|
1517 | if ( attrExpr->get_isType() || attrExpr->get_expr() ) { |
---|
1518 | for ( auto & data : attrList ) { |
---|
1519 | DeclarationWithType * id = data.id; |
---|
1520 | // check if the type is function |
---|
1521 | if ( FunctionType *function = dynamic_cast< FunctionType* >( id->get_type() ) ) { |
---|
1522 | // assume exactly one parameter |
---|
1523 | if ( function->get_parameters().size() == 1 ) { |
---|
1524 | if ( attrExpr->get_isType() ) { |
---|
1525 | resolveAttr( data, function, attrExpr->get_type(), env, altFinder); |
---|
1526 | } else { |
---|
1527 | AlternativeFinder finder( indexer, env ); |
---|
1528 | finder.find( attrExpr->get_expr() ); |
---|
1529 | for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) { |
---|
1530 | if ( choice->expr->get_result()->size() == 1 ) { |
---|
1531 | resolveAttr(data, function, choice->expr->get_result(), choice->env, altFinder ); |
---|
1532 | } // fi |
---|
1533 | } // for |
---|
1534 | } // if |
---|
1535 | } // if |
---|
1536 | } // if |
---|
1537 | } // for |
---|
1538 | } else { |
---|
1539 | for ( auto & data : attrList ) { |
---|
1540 | Cost cost = Cost::zero; |
---|
1541 | Expression * newExpr = data.combine( cost ); |
---|
1542 | alternatives.push_back( Alternative( newExpr, env, Cost::zero, cost ) ); |
---|
1543 | renameTypes( alternatives.back().expr ); |
---|
1544 | } // for |
---|
1545 | } // if |
---|
1546 | } |
---|
1547 | |
---|
1548 | void AlternativeFinder::Finder::postvisit( LogicalExpr *logicalExpr ) { |
---|
1549 | AlternativeFinder firstFinder( indexer, env ); |
---|
1550 | firstFinder.findWithAdjustment( logicalExpr->get_arg1() ); |
---|
1551 | if ( firstFinder.alternatives.empty() ) return; |
---|
1552 | AlternativeFinder secondFinder( indexer, env ); |
---|
1553 | secondFinder.findWithAdjustment( logicalExpr->get_arg2() ); |
---|
1554 | if ( secondFinder.alternatives.empty() ) return; |
---|
1555 | for ( const Alternative & first : firstFinder.alternatives ) { |
---|
1556 | for ( const Alternative & second : secondFinder.alternatives ) { |
---|
1557 | TypeEnvironment compositeEnv; |
---|
1558 | compositeEnv.simpleCombine( first.env ); |
---|
1559 | compositeEnv.simpleCombine( second.env ); |
---|
1560 | |
---|
1561 | LogicalExpr *newExpr = new LogicalExpr( first.expr->clone(), second.expr->clone(), logicalExpr->get_isAnd() ); |
---|
1562 | alternatives.push_back( Alternative( newExpr, compositeEnv, first.cost + second.cost ) ); |
---|
1563 | } |
---|
1564 | } |
---|
1565 | } |
---|
1566 | |
---|
1567 | void AlternativeFinder::Finder::postvisit( ConditionalExpr *conditionalExpr ) { |
---|
1568 | // find alternatives for condition |
---|
1569 | AlternativeFinder firstFinder( indexer, env ); |
---|
1570 | firstFinder.findWithAdjustment( conditionalExpr->arg1 ); |
---|
1571 | if ( firstFinder.alternatives.empty() ) return; |
---|
1572 | // find alternatives for true expression |
---|
1573 | AlternativeFinder secondFinder( indexer, env ); |
---|
1574 | secondFinder.findWithAdjustment( conditionalExpr->arg2 ); |
---|
1575 | if ( secondFinder.alternatives.empty() ) return; |
---|
1576 | // find alterantives for false expression |
---|
1577 | AlternativeFinder thirdFinder( indexer, env ); |
---|
1578 | thirdFinder.findWithAdjustment( conditionalExpr->arg3 ); |
---|
1579 | if ( thirdFinder.alternatives.empty() ) return; |
---|
1580 | for ( const Alternative & first : firstFinder.alternatives ) { |
---|
1581 | for ( const Alternative & second : secondFinder.alternatives ) { |
---|
1582 | for ( const Alternative & third : thirdFinder.alternatives ) { |
---|
1583 | TypeEnvironment compositeEnv; |
---|
1584 | compositeEnv.simpleCombine( first.env ); |
---|
1585 | compositeEnv.simpleCombine( second.env ); |
---|
1586 | compositeEnv.simpleCombine( third.env ); |
---|
1587 | |
---|
1588 | // unify true and false types, then infer parameters to produce new alternatives |
---|
1589 | OpenVarSet openVars; |
---|
1590 | AssertionSet needAssertions, haveAssertions; |
---|
1591 | Alternative newAlt( 0, compositeEnv, first.cost + second.cost + third.cost ); |
---|
1592 | Type* commonType = nullptr; |
---|
1593 | if ( unify( second.expr->result, third.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) { |
---|
1594 | ConditionalExpr *newExpr = new ConditionalExpr( first.expr->clone(), second.expr->clone(), third.expr->clone() ); |
---|
1595 | newExpr->result = commonType ? commonType : second.expr->result->clone(); |
---|
1596 | // convert both options to the conditional result type |
---|
1597 | newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env ); |
---|
1598 | newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env ); |
---|
1599 | newAlt.expr = newExpr; |
---|
1600 | inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) ); |
---|
1601 | } // if |
---|
1602 | } // for |
---|
1603 | } // for |
---|
1604 | } // for |
---|
1605 | } |
---|
1606 | |
---|
1607 | void AlternativeFinder::Finder::postvisit( CommaExpr *commaExpr ) { |
---|
1608 | TypeEnvironment newEnv( env ); |
---|
1609 | Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv ); |
---|
1610 | AlternativeFinder secondFinder( indexer, newEnv ); |
---|
1611 | secondFinder.findWithAdjustment( commaExpr->get_arg2() ); |
---|
1612 | for ( const Alternative & alt : secondFinder.alternatives ) { |
---|
1613 | alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt.expr->clone() ), alt.env, alt.cost ) ); |
---|
1614 | } // for |
---|
1615 | delete newFirstArg; |
---|
1616 | } |
---|
1617 | |
---|
1618 | void AlternativeFinder::Finder::postvisit( RangeExpr * rangeExpr ) { |
---|
1619 | // resolve low and high, accept alternatives whose low and high types unify |
---|
1620 | AlternativeFinder firstFinder( indexer, env ); |
---|
1621 | firstFinder.findWithAdjustment( rangeExpr->low ); |
---|
1622 | if ( firstFinder.alternatives.empty() ) return; |
---|
1623 | AlternativeFinder secondFinder( indexer, env ); |
---|
1624 | secondFinder.findWithAdjustment( rangeExpr->high ); |
---|
1625 | if ( secondFinder.alternatives.empty() ) return; |
---|
1626 | for ( const Alternative & first : firstFinder.alternatives ) { |
---|
1627 | for ( const Alternative & second : secondFinder.alternatives ) { |
---|
1628 | TypeEnvironment compositeEnv; |
---|
1629 | compositeEnv.simpleCombine( first.env ); |
---|
1630 | compositeEnv.simpleCombine( second.env ); |
---|
1631 | OpenVarSet openVars; |
---|
1632 | AssertionSet needAssertions, haveAssertions; |
---|
1633 | Alternative newAlt( 0, compositeEnv, first.cost + second.cost ); |
---|
1634 | Type* commonType = nullptr; |
---|
1635 | if ( unify( first.expr->result, second.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) { |
---|
1636 | RangeExpr * newExpr = new RangeExpr( first.expr->clone(), second.expr->clone() ); |
---|
1637 | newExpr->result = commonType ? commonType : first.expr->result->clone(); |
---|
1638 | newAlt.expr = newExpr; |
---|
1639 | inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) ); |
---|
1640 | } // if |
---|
1641 | } // for |
---|
1642 | } // for |
---|
1643 | } |
---|
1644 | |
---|
1645 | void AlternativeFinder::Finder::postvisit( UntypedTupleExpr *tupleExpr ) { |
---|
1646 | std::vector< AlternativeFinder > subExprAlternatives; |
---|
1647 | altFinder.findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), |
---|
1648 | back_inserter( subExprAlternatives ) ); |
---|
1649 | std::vector< AltList > possibilities; |
---|
1650 | combos( subExprAlternatives.begin(), subExprAlternatives.end(), |
---|
1651 | back_inserter( possibilities ) ); |
---|
1652 | for ( const AltList& alts : possibilities ) { |
---|
1653 | std::list< Expression * > exprs; |
---|
1654 | makeExprList( alts, exprs ); |
---|
1655 | |
---|
1656 | TypeEnvironment compositeEnv; |
---|
1657 | simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv ); |
---|
1658 | alternatives.push_back( |
---|
1659 | Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } ); |
---|
1660 | } // for |
---|
1661 | } |
---|
1662 | |
---|
1663 | void AlternativeFinder::Finder::postvisit( TupleExpr *tupleExpr ) { |
---|
1664 | alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) ); |
---|
1665 | } |
---|
1666 | |
---|
1667 | void AlternativeFinder::Finder::postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ) { |
---|
1668 | alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) ); |
---|
1669 | } |
---|
1670 | |
---|
1671 | void AlternativeFinder::Finder::postvisit( ConstructorExpr * ctorExpr ) { |
---|
1672 | AlternativeFinder finder( indexer, env ); |
---|
1673 | // don't prune here, since it's guaranteed all alternatives will have the same type |
---|
1674 | // (giving the alternatives different types is half of the point of ConstructorExpr nodes) |
---|
1675 | finder.findWithoutPrune( ctorExpr->get_callExpr() ); |
---|
1676 | for ( Alternative & alt : finder.alternatives ) { |
---|
1677 | alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) ); |
---|
1678 | } |
---|
1679 | } |
---|
1680 | |
---|
1681 | void AlternativeFinder::Finder::postvisit( TupleIndexExpr *tupleExpr ) { |
---|
1682 | alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) ); |
---|
1683 | } |
---|
1684 | |
---|
1685 | void AlternativeFinder::Finder::postvisit( TupleAssignExpr *tupleAssignExpr ) { |
---|
1686 | alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) ); |
---|
1687 | } |
---|
1688 | |
---|
1689 | void AlternativeFinder::Finder::postvisit( UniqueExpr *unqExpr ) { |
---|
1690 | AlternativeFinder finder( indexer, env ); |
---|
1691 | finder.findWithAdjustment( unqExpr->get_expr() ); |
---|
1692 | for ( Alternative & alt : finder.alternatives ) { |
---|
1693 | // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked" |
---|
1694 | UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() ); |
---|
1695 | alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) ); |
---|
1696 | } |
---|
1697 | } |
---|
1698 | |
---|
1699 | void AlternativeFinder::Finder::postvisit( StmtExpr *stmtExpr ) { |
---|
1700 | StmtExpr * newStmtExpr = stmtExpr->clone(); |
---|
1701 | ResolvExpr::resolveStmtExpr( newStmtExpr, indexer ); |
---|
1702 | // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr... |
---|
1703 | alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) ); |
---|
1704 | } |
---|
1705 | |
---|
1706 | void AlternativeFinder::Finder::postvisit( UntypedInitExpr *initExpr ) { |
---|
1707 | // handle each option like a cast |
---|
1708 | AltList candidates; |
---|
1709 | PRINT( |
---|
1710 | std::cerr << "untyped init expr: " << initExpr << std::endl; |
---|
1711 | ) |
---|
1712 | // O(N^2) checks of d-types with e-types |
---|
1713 | for ( InitAlternative & initAlt : initExpr->get_initAlts() ) { |
---|
1714 | Type * toType = resolveTypeof( initAlt.type->clone(), indexer ); |
---|
1715 | SymTab::validateType( toType, &indexer ); |
---|
1716 | adjustExprType( toType, env, indexer ); |
---|
1717 | // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else |
---|
1718 | // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving |
---|
1719 | // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal. |
---|
1720 | AlternativeFinder finder( indexer, env ); |
---|
1721 | finder.targetType = toType; |
---|
1722 | finder.findWithAdjustment( initExpr->expr ); |
---|
1723 | for ( Alternative & alt : finder.get_alternatives() ) { |
---|
1724 | TypeEnvironment newEnv( alt.env ); |
---|
1725 | AssertionSet needAssertions, haveAssertions; |
---|
1726 | OpenVarSet openVars; // find things in env that don't have a "representative type" and claim those are open vars? |
---|
1727 | PRINT( |
---|
1728 | std::cerr << " @ " << toType << " " << initAlt.designation << std::endl; |
---|
1729 | ) |
---|
1730 | // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a |
---|
1731 | // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results |
---|
1732 | // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast |
---|
1733 | // to. |
---|
1734 | int discardedValues = alt.expr->result->size() - toType->size(); |
---|
1735 | if ( discardedValues < 0 ) continue; |
---|
1736 | // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not |
---|
1737 | // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3])) |
---|
1738 | // unification run for side-effects |
---|
1739 | unify( toType, alt.expr->result, newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type?? |
---|
1740 | |
---|
1741 | Cost thisCost = castCost( alt.expr->result, toType, indexer, newEnv ); |
---|
1742 | if ( thisCost != Cost::infinity ) { |
---|
1743 | // count one safe conversion for each value that is thrown away |
---|
1744 | thisCost.incSafe( discardedValues ); |
---|
1745 | Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType, true ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost ); |
---|
1746 | inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); |
---|
1747 | } |
---|
1748 | } |
---|
1749 | } |
---|
1750 | |
---|
1751 | // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the |
---|
1752 | // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice |
---|
1753 | // selects first based on argument cost, then on conversion cost. |
---|
1754 | AltList minArgCost; |
---|
1755 | findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) ); |
---|
1756 | findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) ); |
---|
1757 | } |
---|
1758 | |
---|
1759 | void AlternativeFinder::Finder::postvisit( InitExpr * ) { |
---|
1760 | assertf( false, "AlternativeFinder should never see a resolved InitExpr." ); |
---|
1761 | } |
---|
1762 | |
---|
1763 | void AlternativeFinder::Finder::postvisit( DeletedExpr * ) { |
---|
1764 | assertf( false, "AlternativeFinder should never see a DeletedExpr." ); |
---|
1765 | } |
---|
1766 | |
---|
1767 | void AlternativeFinder::Finder::postvisit( GenericExpr * ) { |
---|
1768 | assertf( false, "_Generic is not yet supported." ); |
---|
1769 | } |
---|
1770 | } // namespace ResolvExpr |
---|
1771 | |
---|
1772 | // Local Variables: // |
---|
1773 | // tab-width: 4 // |
---|
1774 | // mode: c++ // |
---|
1775 | // compile-command: "make install" // |
---|
1776 | // End: // |
---|