source: src/ResolvExpr/AlternativeFinder.cc @ 432ce7a

arm-ehjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since 432ce7a was 432ce7a, checked in by Aaron Moss <a3moss@…>, 2 years ago

Port CandidateFinder::postvisit for UntypedExpr?, stub dependencies

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