source: src/ResolvExpr/AlternativeFinder.cc @ 033ff37

arm-ehjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since 033ff37 was 033ff37, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago

remove attribute expression '@'name mechanism

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