source: src/ResolvExpr/AlternativeFinder.cc@ 0c13238

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr no_list persistent-indexer pthread-emulation qualifiedEnum
Last change on this file since 0c13238 was da6032af, checked in by Aaron Moss <a3moss@…>, 7 years ago

Remove assertion cost from cost model

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