source: src/ResolvExpr/AlternativeFinder.cc @ 4d2d45f

arm-ehcleanup-dtorsjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since 4d2d45f was 4d2d45f, checked in by Aaron Moss <a3moss@…>, 3 years ago

Improve assertion error messages

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