source: src/ResolvExpr/AlternativeFinder.cc@ e068c8a

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since e068c8a was ac2b598, checked in by Thierry Delisle <tdelisle@…>, 6 years ago

Changed descriptors for concurrency to use $ prefix instead of trailing _desc

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