source: src/ResolvExpr/AlternativeFinder.cc @ 30ee9ef

aaron-thesisarm-ehcleanup-dtorsdeferred_resnjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexer
Last change on this file since 30ee9ef was 30ee9ef, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago

print error for indexed access to struct fields

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