source: src/ResolvExpr/AlternativeFinder.cc @ 2a6c115

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerwith_gc
Last change on this file since 2a6c115 was 2a6c115, checked in by Rob Schluntz <rschlunt@…>, 4 years ago

Simplify tuple index resolution

  • Property mode set to 100644
File size: 73.5 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 : Sat Feb 17 11:19:39 2018
13// Update Count     : 33
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 "Alternative.h"           // for AltList, Alternative
28#include "AlternativeFinder.h"
29#include "Common/SemanticError.h"  // for SemanticError
30#include "Common/utility.h"        // for deleteAll, printAll, CodeLocation
31#include "Cost.h"                  // for Cost, Cost::zero, operator<<, Cost...
32#include "ExplodedActual.h"        // for ExplodedActual
33#include "InitTweak/InitTweak.h"   // for getFunctionName
34#include "RenameVars.h"            // for RenameVars, global_renamer
35#include "ResolveTypeof.h"         // for resolveTypeof
36#include "Resolver.h"              // for resolveStmtExpr
37#include "SymTab/Indexer.h"        // for Indexer
38#include "SymTab/Mangler.h"        // for Mangler
39#include "SymTab/Validate.h"       // for validateType
40#include "SynTree/Constant.h"      // for Constant
41#include "SynTree/Declaration.h"   // for DeclarationWithType, TypeDecl, Dec...
42#include "SynTree/Expression.h"    // for Expression, CastExpr, NameExpr
43#include "SynTree/Initializer.h"   // for SingleInit, operator<<, Designation
44#include "SynTree/SynTree.h"       // for UniqueId
45#include "SynTree/Type.h"          // for Type, FunctionType, PointerType
46#include "Tuples/Explode.h"        // for explode
47#include "Tuples/Tuples.h"         // for isTtype, handleTupleAssignment
48#include "Unify.h"                 // for unify
49#include "typeops.h"               // for adjustExprType, polyCost, castCost
50
51extern bool resolvep;
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                        Type * formalType = (*formal)->get_type();
440                        convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
441                        ++formal; // can't be in for-loop update because of the continue
442                }
443                if ( formal != formals.end() ) {
444                        return Cost::infinity;
445                }
446
447                for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
448                        convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
449                }
450
451                return convCost;
452        }
453
454        /// Adds type variables to the open variable set and marks their assertions
455        void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
456                for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) {
457                        unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar };
458                        for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->assertions.begin(); assert != (*tyvar)->assertions.end(); ++assert ) {
459                                needAssertions[ *assert ].isUsed = true;
460                        }
461///     needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
462                }
463        }
464
465        static const int recursionLimit = /*10*/ 4;  ///< Limit to depth of recursion satisfaction
466
467        void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
468                for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
469                        if ( i->second.isUsed ) {
470                                indexer.addId( i->first );
471                        }
472                }
473        }
474
475        template< typename ForwardIterator, typename OutputIterator >
476        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 ) {
477                if ( begin == end ) {
478                        if ( newNeed.empty() ) {
479                                PRINT(
480                                        std::cerr << "all assertions satisfied, output alternative: ";
481                                        newAlt.print( std::cerr );
482                                        std::cerr << std::endl;
483                                );
484                                *out++ = newAlt;
485                                return;
486                        } else if ( level >= recursionLimit ) {
487                                SemanticError( newAlt.expr->location, "Too many recursive assertions" );
488                        } else {
489                                AssertionSet newerNeed;
490                                PRINT(
491                                        std::cerr << "recursing with new set:" << std::endl;
492                                        printAssertionSet( newNeed, std::cerr, 8 );
493                                )
494                                inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, level+1, indexer, out );
495                                return;
496                        }
497                }
498
499                ForwardIterator cur = begin++;
500                if ( ! cur->second.isUsed ) {
501                        inferRecursive( begin, end, newAlt, openVars, decls, newNeed, level, indexer, out );
502                        return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
503                }
504                DeclarationWithType *curDecl = cur->first;
505
506                PRINT(
507                        std::cerr << "inferRecursive: assertion is ";
508                        curDecl->print( std::cerr );
509                        std::cerr << std::endl;
510                )
511                std::list< SymTab::Indexer::IdData > candidates;
512                decls.lookupId( curDecl->get_name(), candidates );
513///   if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
514                for ( const auto & data : candidates ) {
515                        DeclarationWithType * candidate = data.id;
516                        PRINT(
517                                std::cerr << "inferRecursive: candidate is ";
518                                candidate->print( std::cerr );
519                                std::cerr << std::endl;
520                        )
521
522                        AssertionSet newHave, newerNeed( newNeed );
523                        TypeEnvironment newEnv( newAlt.env );
524                        OpenVarSet newOpenVars( openVars );
525                        Type *adjType = candidate->get_type()->clone();
526                        adjustExprType( adjType, newEnv, indexer );
527                        renameTyVars( adjType );
528                        PRINT(
529                                std::cerr << "unifying ";
530                                curDecl->get_type()->print( std::cerr );
531                                std::cerr << " with ";
532                                adjType->print( std::cerr );
533                                std::cerr << std::endl;
534                        )
535                        if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
536                                PRINT(
537                                        std::cerr << "success!" << std::endl;
538                                )
539                                SymTab::Indexer newDecls( decls );
540                                addToIndexer( newHave, newDecls );
541                                Alternative newerAlt( newAlt );
542                                newerAlt.env = newEnv;
543                                assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
544
545                                // everything with an empty idChain was pulled in by the current assertion.
546                                // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
547                                for ( auto & a : newerNeed ) {
548                                        if ( a.second.idChain.empty() ) {
549                                                a.second.idChain = cur->second.idChain;
550                                                a.second.idChain.push_back( curDecl->get_uniqueId() );
551                                        }
552                                }
553
554                                Expression *varExpr = data.combine( newerAlt.cvtCost );
555                                delete varExpr->get_result();
556                                varExpr->set_result( adjType->clone() );
557                                PRINT(
558                                        std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
559                                        curDecl->print( std::cerr );
560                                        std::cerr << " with declaration " << candidate->get_uniqueId() << " ";
561                                        candidate->print( std::cerr );
562                                        std::cerr << std::endl;
563                                )
564                                // 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).
565                                InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
566                                for ( UniqueId id : cur->second.idChain ) {
567                                        inferParameters = (*inferParameters)[ id ].inferParams.get();
568                                }
569                                // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
570                                (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( candidate->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
571                                inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, level, indexer, out );
572                        } else {
573                                delete adjType;
574                        }
575                }
576        }
577
578        template< typename OutputIterator >
579        void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
580//      PRINT(
581//          std::cerr << "inferParameters: assertions needed are" << std::endl;
582//          printAll( need, std::cerr, 8 );
583//          )
584                SymTab::Indexer decls( indexer );
585                // PRINT(
586                //      std::cerr << "============= original indexer" << std::endl;
587                //      indexer.print( std::cerr );
588                //      std::cerr << "============= new indexer" << std::endl;
589                //      decls.print( std::cerr );
590                // )
591                addToIndexer( have, decls );
592                AssertionSet newNeed;
593                PRINT(
594                        std::cerr << "env is: " << std::endl;
595                        newAlt.env.print( std::cerr, 0 );
596                        std::cerr << std::endl;
597                )
598
599                inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out );
600//      PRINT(
601//          std::cerr << "declaration 14 is ";
602//          Declaration::declFromId
603//          *out++ = newAlt;
604//          )
605        }
606
607        /// Gets a default value from an initializer, nullptr if not present
608        ConstantExpr* getDefaultValue( Initializer* init ) {
609                if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) {
610                        if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->value ) ) {
611                                return dynamic_cast<ConstantExpr*>( ce->arg );
612                        } else {
613                                return dynamic_cast<ConstantExpr*>( si->value );
614                        }
615                }
616                return nullptr;
617        }
618
619        /// State to iteratively build a match of parameter expressions to arguments
620        struct ArgPack {
621                std::size_t parent;                ///< Index of parent pack
622                std::unique_ptr<Expression> expr;  ///< The argument stored here
623                Cost cost;                         ///< The cost of this argument
624                TypeEnvironment env;               ///< Environment for this pack
625                AssertionSet need;                 ///< Assertions outstanding for this pack
626                AssertionSet have;                 ///< Assertions found for this pack
627                OpenVarSet openVars;               ///< Open variables for this pack
628                unsigned nextArg;                  ///< Index of next argument in arguments list
629                unsigned tupleStart;               ///< Number of tuples that start at this index
630                unsigned nextExpl;                 ///< Index of next exploded element
631                unsigned explAlt;                  ///< Index of alternative for nextExpl > 0
632
633                ArgPack()
634                        : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
635                          tupleStart(0), nextExpl(0), explAlt(0) {}
636
637                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
638                                const OpenVarSet& openVars)
639                        : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
640                          openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
641
642                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
643                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
644                                unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
645                                unsigned explAlt = 0 )
646                        : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
647                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
648                          nextExpl(nextExpl), explAlt(explAlt) {}
649
650                ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
651                                OpenVarSet&& openVars, unsigned nextArg, Cost added )
652                        : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added),
653                          env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)),
654                          nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
655
656                /// true iff this pack is in the middle of an exploded argument
657                bool hasExpl() const { return nextExpl > 0; }
658
659                /// Gets the list of exploded alternatives for this pack
660                const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
661                        return args[nextArg-1][explAlt];
662                }
663
664                /// Ends a tuple expression, consolidating the appropriate actuals
665                void endTuple( const std::vector<ArgPack>& packs ) {
666                        // add all expressions in tuple to list, summing cost
667                        std::list<Expression*> exprs;
668                        const ArgPack* pack = this;
669                        if ( expr ) { exprs.push_front( expr.release() ); }
670                        while ( pack->tupleStart == 0 ) {
671                                pack = &packs[pack->parent];
672                                exprs.push_front( pack->expr->clone() );
673                                cost += pack->cost;
674                        }
675                        // reset pack to appropriate tuple
676                        expr.reset( new TupleExpr( exprs ) );
677                        tupleStart = pack->tupleStart - 1;
678                        parent = pack->parent;
679                }
680        };
681
682        /// Instantiates an argument to match a formal, returns false if no results left
683        bool instantiateArgument( Type* formalType, Initializer* initializer,
684                        const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
685                        const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
686                if ( TupleType * tupleType = dynamic_cast<TupleType*>( formalType ) ) {
687                        // formalType is a TupleType - group actuals into a TupleExpr
688                        ++nTuples;
689                        for ( Type* type : *tupleType ) {
690                                // xxx - dropping initializer changes behaviour from previous, but seems correct
691                                // ^^^ need to handle the case where a tuple has a default argument
692                                if ( ! instantiateArgument(
693                                                type, nullptr, args, results, genStart, indexer, nTuples ) )
694                                        return false;
695                                nTuples = 0;
696                        }
697                        // re-consititute tuples for final generation
698                        for ( auto i = genStart; i < results.size(); ++i ) {
699                                results[i].endTuple( results );
700                        }
701                        return true;
702                } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
703                        // formalType is a ttype, consumes all remaining arguments
704                        // xxx - mixing default arguments with variadic??
705
706                        // completed tuples; will be spliced to end of results to finish
707                        std::vector<ArgPack> finalResults{};
708
709                        // iterate until all results completed
710                        std::size_t genEnd;
711                        ++nTuples;
712                        do {
713                                genEnd = results.size();
714
715                                // add another argument to results
716                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
717                                        auto nextArg = results[i].nextArg;
718
719                                        // use next element of exploded tuple if present
720                                        if ( results[i].hasExpl() ) {
721                                                const ExplodedActual& expl = results[i].getExpl( args );
722
723                                                unsigned nextExpl = results[i].nextExpl + 1;
724                                                if ( nextExpl == expl.exprs.size() ) {
725                                                        nextExpl = 0;
726                                                }
727
728                                                results.emplace_back(
729                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
730                                                        copy(results[i].need), copy(results[i].have),
731                                                        copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
732                                                        results[i].explAlt );
733
734                                                continue;
735                                        }
736
737                                        // finish result when out of arguments
738                                        if ( nextArg >= args.size() ) {
739                                                ArgPack newResult{
740                                                        results[i].env, results[i].need, results[i].have,
741                                                        results[i].openVars };
742                                                newResult.nextArg = nextArg;
743                                                Type* argType;
744
745                                                if ( nTuples > 0 || ! results[i].expr ) {
746                                                        // first iteration or no expression to clone,
747                                                        // push empty tuple expression
748                                                        newResult.parent = i;
749                                                        std::list<Expression*> emptyList;
750                                                        newResult.expr.reset( new TupleExpr( emptyList ) );
751                                                        argType = newResult.expr->get_result();
752                                                } else {
753                                                        // clone result to collect tuple
754                                                        newResult.parent = results[i].parent;
755                                                        newResult.cost = results[i].cost;
756                                                        newResult.tupleStart = results[i].tupleStart;
757                                                        newResult.expr.reset( results[i].expr->clone() );
758                                                        argType = newResult.expr->get_result();
759
760                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
761                                                                // the case where a ttype value is passed directly is special,
762                                                                // e.g. for argument forwarding purposes
763                                                                // xxx - what if passing multiple arguments, last of which is
764                                                                //       ttype?
765                                                                // xxx - what would happen if unify was changed so that unifying
766                                                                //       tuple
767                                                                // types flattened both before unifying lists? then pass in
768                                                                // TupleType (ttype) below.
769                                                                --newResult.tupleStart;
770                                                        } else {
771                                                                // collapse leftover arguments into tuple
772                                                                newResult.endTuple( results );
773                                                                argType = newResult.expr->get_result();
774                                                        }
775                                                }
776
777                                                // check unification for ttype before adding to final
778                                                if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
779                                                                newResult.openVars, indexer ) ) {
780                                                        finalResults.push_back( move(newResult) );
781                                                }
782
783                                                continue;
784                                        }
785
786                                        // add each possible next argument
787                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
788                                                const ExplodedActual& expl = args[nextArg][j];
789
790                                                // fresh copies of parent parameters for this iteration
791                                                TypeEnvironment env = results[i].env;
792                                                OpenVarSet openVars = results[i].openVars;
793
794                                                env.addActual( expl.env, openVars );
795
796                                                // skip empty tuple arguments by (near-)cloning parent into next gen
797                                                if ( expl.exprs.empty() ) {
798                                                        results.emplace_back(
799                                                                results[i], move(env), copy(results[i].need),
800                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
801
802                                                        continue;
803                                                }
804
805                                                // add new result
806                                                results.emplace_back(
807                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
808                                                        copy(results[i].have), move(openVars), nextArg + 1,
809                                                        nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
810                                        }
811                                }
812
813                                // reset for next round
814                                genStart = genEnd;
815                                nTuples = 0;
816                        } while ( genEnd != results.size() );
817
818                        // splice final results onto results
819                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
820                                results.push_back( move(finalResults[i]) );
821                        }
822                        return ! finalResults.empty();
823                }
824
825                // iterate each current subresult
826                std::size_t genEnd = results.size();
827                for ( std::size_t i = genStart; i < genEnd; ++i ) {
828                        auto nextArg = results[i].nextArg;
829
830                        // use remainder of exploded tuple if present
831                        if ( results[i].hasExpl() ) {
832                                const ExplodedActual& expl = results[i].getExpl( args );
833                                Expression* expr = expl.exprs[results[i].nextExpl].get();
834
835                                TypeEnvironment env = results[i].env;
836                                AssertionSet need = results[i].need, have = results[i].have;
837                                OpenVarSet openVars = results[i].openVars;
838
839                                Type* actualType = expr->get_result();
840
841                                PRINT(
842                                        std::cerr << "formal type is ";
843                                        formalType->print( std::cerr );
844                                        std::cerr << std::endl << "actual type is ";
845                                        actualType->print( std::cerr );
846                                        std::cerr << std::endl;
847                                )
848
849                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
850                                        unsigned nextExpl = results[i].nextExpl + 1;
851                                        if ( nextExpl == expl.exprs.size() ) {
852                                                nextExpl = 0;
853                                        }
854
855                                        results.emplace_back(
856                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg,
857                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
858                                }
859
860                                continue;
861                        }
862
863                        // use default initializers if out of arguments
864                        if ( nextArg >= args.size() ) {
865                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
866                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
867                                                TypeEnvironment env = results[i].env;
868                                                AssertionSet need = results[i].need, have = results[i].have;
869                                                OpenVarSet openVars = results[i].openVars;
870
871                                                if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
872                                                                indexer ) ) {
873                                                        results.emplace_back(
874                                                                i, cnstExpr, move(env), move(need), move(have),
875                                                                move(openVars), nextArg, nTuples );
876                                                }
877                                        }
878                                }
879
880                                continue;
881                        }
882
883                        // Check each possible next argument
884                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
885                                const ExplodedActual& expl = args[nextArg][j];
886
887                                // fresh copies of parent parameters for this iteration
888                                TypeEnvironment env = results[i].env;
889                                AssertionSet need = results[i].need, have = results[i].have;
890                                OpenVarSet openVars = results[i].openVars;
891
892                                env.addActual( expl.env, openVars );
893
894                                // skip empty tuple arguments by (near-)cloning parent into next gen
895                                if ( expl.exprs.empty() ) {
896                                        results.emplace_back(
897                                                results[i], move(env), move(need), move(have), move(openVars),
898                                                nextArg + 1, expl.cost );
899
900                                        continue;
901                                }
902
903                                // consider only first exploded actual
904                                Expression* expr = expl.exprs.front().get();
905                                Type* actualType = expr->result->clone();
906
907                                PRINT(
908                                        std::cerr << "formal type is ";
909                                        formalType->print( std::cerr );
910                                        std::cerr << std::endl << "actual type is ";
911                                        actualType->print( std::cerr );
912                                        std::cerr << std::endl;
913                                )
914
915                                // attempt to unify types
916                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
917                                        // add new result
918                                        results.emplace_back(
919                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
920                                                nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
921                                }
922                        }
923                }
924
925                // reset for next parameter
926                genStart = genEnd;
927
928                return genEnd != results.size();
929        }
930
931        template<typename OutputIterator>
932        void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, ArgPack& result,
933                        const std::vector<ArgPack>& results, OutputIterator out ) {
934                ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
935                // sum cost and accumulate actuals
936                std::list<Expression*>& args = appExpr->args;
937                Cost cost = func.cost;
938                const ArgPack* pack = &result;
939                while ( pack->expr ) {
940                        args.push_front( pack->expr->clone() );
941                        cost += pack->cost;
942                        pack = &results[pack->parent];
943                }
944                // build and validate new alternative
945                Alternative newAlt( appExpr, result.env, cost );
946                PRINT(
947                        std::cerr << "instantiate function success: " << appExpr << std::endl;
948                        std::cerr << "need assertions:" << std::endl;
949                        printAssertionSet( result.need, std::cerr, 8 );
950                )
951                inferParameters( result.need, result.have, newAlt, result.openVars, out );
952        }
953
954        template<typename OutputIterator>
955        void AlternativeFinder::Finder::makeFunctionAlternatives( const Alternative &func,
956                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
957                OpenVarSet funcOpenVars;
958                AssertionSet funcNeed, funcHave;
959                TypeEnvironment funcEnv( func.env );
960                makeUnifiableVars( funcType, funcOpenVars, funcNeed );
961                // add all type variables as open variables now so that those not used in the parameter
962                // list are still considered open.
963                funcEnv.add( funcType->forall );
964
965                if ( targetType && ! targetType->isVoid() && ! funcType->returnVals.empty() ) {
966                        // attempt to narrow based on expected target type
967                        Type * returnType = funcType->returnVals.front()->get_type();
968                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
969                                        indexer ) ) {
970                                // unification failed, don't pursue this function alternative
971                                return;
972                        }
973                }
974
975                // iteratively build matches, one parameter at a time
976                std::vector<ArgPack> results;
977                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
978                std::size_t genStart = 0;
979
980                for ( DeclarationWithType* formal : funcType->parameters ) {
981                        ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
982                        if ( ! instantiateArgument(
983                                        obj->type, obj->init, args, results, genStart, indexer ) )
984                                return;
985                }
986
987                if ( funcType->get_isVarArgs() ) {
988                        // append any unused arguments to vararg pack
989                        std::size_t genEnd;
990                        do {
991                                genEnd = results.size();
992
993                                // iterate results
994                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
995                                        auto nextArg = results[i].nextArg;
996
997                                        // use remainder of exploded tuple if present
998                                        if ( results[i].hasExpl() ) {
999                                                const ExplodedActual& expl = results[i].getExpl( args );
1000
1001                                                unsigned nextExpl = results[i].nextExpl + 1;
1002                                                if ( nextExpl == expl.exprs.size() ) {
1003                                                        nextExpl = 0;
1004                                                }
1005
1006                                                results.emplace_back(
1007                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
1008                                                        copy(results[i].need), copy(results[i].have),
1009                                                        copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
1010                                                        results[i].explAlt );
1011
1012                                                continue;
1013                                        }
1014
1015                                        // finish result when out of arguments
1016                                        if ( nextArg >= args.size() ) {
1017                                                validateFunctionAlternative( func, results[i], results, out );
1018
1019                                                continue;
1020                                        }
1021
1022                                        // add each possible next argument
1023                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1024                                                const ExplodedActual& expl = args[nextArg][j];
1025
1026                                                // fresh copies of parent parameters for this iteration
1027                                                TypeEnvironment env = results[i].env;
1028                                                OpenVarSet openVars = results[i].openVars;
1029
1030                                                env.addActual( expl.env, openVars );
1031
1032                                                // skip empty tuple arguments by (near-)cloning parent into next gen
1033                                                if ( expl.exprs.empty() ) {
1034                                                        results.emplace_back(
1035                                                                results[i], move(env), copy(results[i].need),
1036                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
1037
1038                                                        continue;
1039                                                }
1040
1041                                                // add new result
1042                                                results.emplace_back(
1043                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
1044                                                        copy(results[i].have), move(openVars), nextArg + 1, 0,
1045                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1046                                        }
1047                                }
1048
1049                                genStart = genEnd;
1050                        } while ( genEnd != results.size() );
1051                } else {
1052                        // filter out results that don't use all the arguments
1053                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
1054                                ArgPack& result = results[i];
1055                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
1056                                        validateFunctionAlternative( func, result, results, out );
1057                                }
1058                        }
1059                }
1060        }
1061
1062        void AlternativeFinder::Finder::postvisit( UntypedExpr *untypedExpr ) {
1063                AlternativeFinder funcFinder( indexer, env );
1064                funcFinder.findWithAdjustment( untypedExpr->function );
1065                // if there are no function alternatives, then proceeding is a waste of time.
1066                // xxx - findWithAdjustment throws, so this check and others like it shouldn't be necessary.
1067                if ( funcFinder.alternatives.empty() ) return;
1068
1069                std::vector< AlternativeFinder > argAlternatives;
1070                altFinder.findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
1071                        back_inserter( argAlternatives ) );
1072
1073                // take care of possible tuple assignments
1074                // if not tuple assignment, assignment is taken care of as a normal function call
1075                Tuples::handleTupleAssignment( altFinder, untypedExpr, argAlternatives );
1076
1077                // find function operators
1078                static NameExpr *opExpr = new NameExpr( "?()" );
1079                AlternativeFinder funcOpFinder( indexer, env );
1080                // it's ok if there aren't any defined function ops
1081                funcOpFinder.maybeFind( opExpr );
1082                PRINT(
1083                        std::cerr << "known function ops:" << std::endl;
1084                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
1085                )
1086
1087                // pre-explode arguments
1088                ExplodedArgs argExpansions;
1089                argExpansions.reserve( argAlternatives.size() );
1090
1091                for ( const AlternativeFinder& arg : argAlternatives ) {
1092                        argExpansions.emplace_back();
1093                        auto& argE = argExpansions.back();
1094                        argE.reserve( arg.alternatives.size() );
1095
1096                        for ( const Alternative& actual : arg ) {
1097                                argE.emplace_back( actual, indexer );
1098                        }
1099                }
1100
1101                AltList candidates;
1102                SemanticErrorException errors;
1103                for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
1104                        try {
1105                                PRINT(
1106                                        std::cerr << "working on alternative: " << std::endl;
1107                                        func->print( std::cerr, 8 );
1108                                )
1109                                // check if the type is pointer to function
1110                                if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->result->stripReferences() ) ) {
1111                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->base ) ) {
1112                                                Alternative newFunc( *func );
1113                                                referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1114                                                makeFunctionAlternatives( newFunc, function, argExpansions,
1115                                                        std::back_inserter( candidates ) );
1116                                        }
1117                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->result->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
1118                                        if ( const EqvClass *eqvClass = func->env.lookup( typeInst->name ) ) {
1119                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass->type ) ) {
1120                                                        Alternative newFunc( *func );
1121                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1122                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1123                                                                std::back_inserter( candidates ) );
1124                                                } // if
1125                                        } // if
1126                                }
1127                        } catch ( SemanticErrorException &e ) {
1128                                errors.append( e );
1129                        }
1130                } // for
1131
1132                // try each function operator ?() with each function alternative
1133                if ( ! funcOpFinder.alternatives.empty() ) {
1134                        // add exploded function alternatives to front of argument list
1135                        std::vector<ExplodedActual> funcE;
1136                        funcE.reserve( funcFinder.alternatives.size() );
1137                        for ( const Alternative& actual : funcFinder ) {
1138                                funcE.emplace_back( actual, indexer );
1139                        }
1140                        argExpansions.insert( argExpansions.begin(), move(funcE) );
1141
1142                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
1143                                        funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
1144                                try {
1145                                        // check if type is a pointer to function
1146                                        if ( PointerType* pointer = dynamic_cast<PointerType*>(
1147                                                        funcOp->expr->result->stripReferences() ) ) {
1148                                                if ( FunctionType* function =
1149                                                                dynamic_cast<FunctionType*>( pointer->base ) ) {
1150                                                        Alternative newFunc( *funcOp );
1151                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1152                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1153                                                                std::back_inserter( candidates ) );
1154                                                }
1155                                        }
1156                                } catch ( SemanticErrorException &e ) {
1157                                        errors.append( e );
1158                                }
1159                        }
1160                }
1161
1162                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
1163                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
1164
1165                // compute conversionsion costs
1166                for ( Alternative& withFunc : candidates ) {
1167                        Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
1168
1169                        PRINT(
1170                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
1171                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->function->result );
1172                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->base );
1173                                std::cerr << "Case +++++++++++++ " << appExpr->function << std::endl;
1174                                std::cerr << "formals are:" << std::endl;
1175                                printAll( function->parameters, std::cerr, 8 );
1176                                std::cerr << "actuals are:" << std::endl;
1177                                printAll( appExpr->args, std::cerr, 8 );
1178                                std::cerr << "bindings are:" << std::endl;
1179                                withFunc.env.print( std::cerr, 8 );
1180                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1181                        )
1182                        if ( cvtCost != Cost::infinity ) {
1183                                withFunc.cvtCost = cvtCost;
1184                                alternatives.push_back( withFunc );
1185                        } // if
1186                } // for
1187
1188                candidates = move(alternatives);
1189
1190                // use a new list so that alternatives are not examined by addAnonConversions twice.
1191                AltList winners;
1192                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
1193
1194                // function may return struct or union value, in which case we need to add alternatives
1195                // for implicitconversions to each of the anonymous members, must happen after findMinCost
1196                // since anon conversions are never the cheapest expression
1197                for ( const Alternative & alt : winners ) {
1198                        addAnonConversions( alt );
1199                }
1200                spliceBegin( alternatives, winners );
1201
1202                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1203                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1204                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1205                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1206                        //   const char * x = "hello world";
1207                        //   unsigned char ch = x[0];
1208                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1209                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1210                        // fix this issue in a more robust way.
1211                        targetType = nullptr;
1212                        postvisit( untypedExpr );
1213                }
1214        }
1215
1216        bool isLvalue( Expression *expr ) {
1217                // xxx - recurse into tuples?
1218                return expr->result && ( expr->result->get_lvalue() || dynamic_cast< ReferenceType * >( expr->result ) );
1219        }
1220
1221        void AlternativeFinder::Finder::postvisit( AddressExpr *addressExpr ) {
1222                AlternativeFinder finder( indexer, env );
1223                finder.find( addressExpr->get_arg() );
1224                for ( Alternative& alt : finder.alternatives ) {
1225                        if ( isLvalue( alt.expr ) ) {
1226                                alternatives.push_back(
1227                                        Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } );
1228                        } // if
1229                } // for
1230        }
1231
1232        void AlternativeFinder::Finder::postvisit( LabelAddressExpr * expr ) {
1233                alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
1234        }
1235
1236        Expression * restructureCast( Expression * argExpr, Type * toType, bool isGenerated ) {
1237                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1238                        // Argument expression is a tuple and the target type is not void and not a reference type.
1239                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
1240                        // cast expressions. If there are more components of the tuple than components in the target type,
1241                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
1242                        // side effects will still be done).
1243                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1244                                // expressions which may contain side effects require a single unique instance of the expression.
1245                                argExpr = new UniqueExpr( argExpr );
1246                        }
1247                        std::list< Expression * > componentExprs;
1248                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
1249                                // cast each component
1250                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1251                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ), isGenerated ) );
1252                        }
1253                        delete argExpr;
1254                        assert( componentExprs.size() > 0 );
1255                        // produce the tuple of casts
1256                        return new TupleExpr( componentExprs );
1257                } else {
1258                        // handle normally
1259                        CastExpr * ret = new CastExpr( argExpr, toType->clone() );
1260                        ret->isGenerated = isGenerated;
1261                        return ret;
1262                }
1263        }
1264
1265        void AlternativeFinder::Finder::postvisit( CastExpr *castExpr ) {
1266                Type *& toType = castExpr->get_result();
1267                assert( toType );
1268                toType = resolveTypeof( toType, indexer );
1269                SymTab::validateType( toType, &indexer );
1270                adjustExprType( toType, env, indexer );
1271
1272                AlternativeFinder finder( indexer, env );
1273                finder.targetType = toType;
1274                finder.findWithAdjustment( castExpr->arg );
1275
1276                AltList candidates;
1277                for ( Alternative & alt : finder.alternatives ) {
1278                        AssertionSet needAssertions, haveAssertions;
1279                        OpenVarSet openVars;
1280
1281                        alt.env.extractOpenVars( openVars );
1282
1283                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1284                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1285                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1286                        // to.
1287                        int discardedValues = alt.expr->result->size() - castExpr->result->size();
1288                        if ( discardedValues < 0 ) continue;
1289                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1290                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1291                        // unification run for side-effects
1292                        unify( castExpr->result, alt.expr->result, alt.env, needAssertions,
1293                                haveAssertions, openVars, indexer );
1294                        Cost thisCost = castCost( alt.expr->result, castExpr->result, indexer,
1295                                alt.env );
1296                        PRINT(
1297                                std::cerr << "working on cast with result: " << castExpr->result << std::endl;
1298                                std::cerr << "and expr type: " << alt.expr->result << std::endl;
1299                                std::cerr << "env: " << alt.env << std::endl;
1300                        )
1301                        if ( thisCost != Cost::infinity ) {
1302                                PRINT(
1303                                        std::cerr << "has finite cost." << std::endl;
1304                                )
1305                                // count one safe conversion for each value that is thrown away
1306                                thisCost.incSafe( discardedValues );
1307                                Alternative newAlt( restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), alt.env,
1308                                        alt.cost, thisCost );
1309                                inferParameters( needAssertions, haveAssertions, newAlt, openVars,
1310                                        back_inserter( candidates ) );
1311                        } // if
1312                } // for
1313
1314                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1315                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1316                // selects first based on argument cost, then on conversion cost.
1317                AltList minArgCost;
1318                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1319                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1320        }
1321
1322        void AlternativeFinder::Finder::postvisit( VirtualCastExpr * castExpr ) {
1323                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
1324                AlternativeFinder finder( indexer, env );
1325                // don't prune here, since it's guaranteed all alternatives will have the same type
1326                finder.findWithoutPrune( castExpr->get_arg() );
1327                for ( Alternative & alt : finder.alternatives ) {
1328                        alternatives.push_back( Alternative(
1329                                new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
1330                                alt.env, alt.cost ) );
1331                }
1332        }
1333
1334        namespace {
1335                /// Gets name from untyped member expression (member must be NameExpr)
1336                const std::string& get_member_name( UntypedMemberExpr *memberExpr ) {
1337                        NameExpr * nameExpr = dynamic_cast< NameExpr * >( memberExpr->get_member() );
1338                        assert( nameExpr );
1339                        return nameExpr->get_name();
1340                }
1341        }
1342
1343        void AlternativeFinder::Finder::postvisit( UntypedMemberExpr *memberExpr ) {
1344                AlternativeFinder funcFinder( indexer, env );
1345                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1346                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1347                        // 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
1348                        Cost cost = agg->cost;
1349                        Expression * aggrExpr = agg->expr->clone();
1350                        referenceToRvalueConversion( aggrExpr, cost );
1351                        std::unique_ptr<Expression> guard( aggrExpr );
1352
1353                        // find member of the given type
1354                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
1355                                addAggMembers( structInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
1356                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
1357                                addAggMembers( unionInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
1358                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1359                                addTupleMembers( tupleType, aggrExpr, cost, agg->env, memberExpr->get_member() );
1360                        } // if
1361                } // for
1362        }
1363
1364        void AlternativeFinder::Finder::postvisit( MemberExpr *memberExpr ) {
1365                alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
1366        }
1367
1368        void AlternativeFinder::Finder::postvisit( NameExpr *nameExpr ) {
1369                std::list< SymTab::Indexer::IdData > declList;
1370                indexer.lookupId( nameExpr->name, declList );
1371                PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
1372                for ( auto & data : declList ) {
1373                        Cost cost = Cost::zero;
1374                        Expression * newExpr = data.combine( cost );
1375
1376                        // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so
1377                        // can't construct in place and use vector::back
1378                        Alternative newAlt( newExpr, env, Cost::zero, cost );
1379                        PRINT(
1380                                std::cerr << "decl is ";
1381                                data.id->print( std::cerr );
1382                                std::cerr << std::endl;
1383                                std::cerr << "newExpr is ";
1384                                newExpr->print( std::cerr );
1385                                std::cerr << std::endl;
1386                        )
1387                        renameTypes( newAlt.expr );
1388                        addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1389                        alternatives.push_back( std::move(newAlt) );
1390                } // for
1391        }
1392
1393        void AlternativeFinder::Finder::postvisit( VariableExpr *variableExpr ) {
1394                // not sufficient to clone here, because variable's type may have changed
1395                // since the VariableExpr was originally created.
1396                alternatives.push_back( Alternative( new VariableExpr( variableExpr->var ), env, Cost::zero ) );
1397        }
1398
1399        void AlternativeFinder::Finder::postvisit( ConstantExpr *constantExpr ) {
1400                alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
1401        }
1402
1403        void AlternativeFinder::Finder::postvisit( SizeofExpr *sizeofExpr ) {
1404                if ( sizeofExpr->get_isType() ) {
1405                        Type * newType = sizeofExpr->get_type()->clone();
1406                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1407                } else {
1408                        // find all alternatives for the argument to sizeof
1409                        AlternativeFinder finder( indexer, env );
1410                        finder.find( sizeofExpr->get_expr() );
1411                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1412                        AltList winners;
1413                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1414                        if ( winners.size() != 1 ) {
1415                                SemanticError( sizeofExpr->get_expr(), "Ambiguous expression in sizeof operand: " );
1416                        } // if
1417                        // return the lowest cost alternative for the argument
1418                        Alternative &choice = winners.front();
1419                        referenceToRvalueConversion( choice.expr, choice.cost );
1420                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1421                } // if
1422        }
1423
1424        void AlternativeFinder::Finder::postvisit( AlignofExpr *alignofExpr ) {
1425                if ( alignofExpr->get_isType() ) {
1426                        Type * newType = alignofExpr->get_type()->clone();
1427                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1428                } else {
1429                        // find all alternatives for the argument to sizeof
1430                        AlternativeFinder finder( indexer, env );
1431                        finder.find( alignofExpr->get_expr() );
1432                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1433                        AltList winners;
1434                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1435                        if ( winners.size() != 1 ) {
1436                                SemanticError( alignofExpr->get_expr(), "Ambiguous expression in alignof operand: " );
1437                        } // if
1438                        // return the lowest cost alternative for the argument
1439                        Alternative &choice = winners.front();
1440                        referenceToRvalueConversion( choice.expr, choice.cost );
1441                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1442                } // if
1443        }
1444
1445        template< typename StructOrUnionType >
1446        void AlternativeFinder::Finder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1447                std::list< Declaration* > members;
1448                aggInst->lookup( name, members );
1449                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1450                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1451                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1452                                renameTypes( alternatives.back().expr );
1453                        } else {
1454                                assert( false );
1455                        }
1456                }
1457        }
1458
1459        void AlternativeFinder::Finder::postvisit( UntypedOffsetofExpr *offsetofExpr ) {
1460                AlternativeFinder funcFinder( indexer, env );
1461                // xxx - resolveTypeof?
1462                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1463                        addOffsetof( structInst, offsetofExpr->member );
1464                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1465                        addOffsetof( unionInst, offsetofExpr->member );
1466                }
1467        }
1468
1469        void AlternativeFinder::Finder::postvisit( OffsetofExpr *offsetofExpr ) {
1470                alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
1471        }
1472
1473        void AlternativeFinder::Finder::postvisit( OffsetPackExpr *offsetPackExpr ) {
1474                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
1475        }
1476
1477        namespace {
1478                void resolveAttr( SymTab::Indexer::IdData data, FunctionType *function, Type *argType, const TypeEnvironment &env, AlternativeFinder & finder ) {
1479                        // assume no polymorphism
1480                        // assume no implicit conversions
1481                        assert( function->get_parameters().size() == 1 );
1482                        PRINT(
1483                                std::cerr << "resolvAttr: funcDecl is ";
1484                                data.id->print( std::cerr );
1485                                std::cerr << " argType is ";
1486                                argType->print( std::cerr );
1487                                std::cerr << std::endl;
1488                        )
1489                        const SymTab::Indexer & indexer = finder.get_indexer();
1490                        AltList & alternatives = finder.get_alternatives();
1491                        if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1492                                Cost cost = Cost::zero;
1493                                Expression * newExpr = data.combine( cost );
1494                                alternatives.push_back( Alternative( new AttrExpr( newExpr, argType->clone() ), env, Cost::zero, cost ) );
1495                                for ( DeclarationWithType * retVal : function->returnVals ) {
1496                                        alternatives.back().expr->result = retVal->get_type()->clone();
1497                                } // for
1498                        } // if
1499                }
1500        }
1501
1502        void AlternativeFinder::Finder::postvisit( AttrExpr *attrExpr ) {
1503                // assume no 'pointer-to-attribute'
1504                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1505                assert( nameExpr );
1506                std::list< SymTab::Indexer::IdData > attrList;
1507                indexer.lookupId( nameExpr->get_name(), attrList );
1508                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1509                        for ( auto & data : attrList ) {
1510                                DeclarationWithType * id = data.id;
1511                                // check if the type is function
1512                                if ( FunctionType *function = dynamic_cast< FunctionType* >( id->get_type() ) ) {
1513                                        // assume exactly one parameter
1514                                        if ( function->get_parameters().size() == 1 ) {
1515                                                if ( attrExpr->get_isType() ) {
1516                                                        resolveAttr( data, function, attrExpr->get_type(), env, altFinder);
1517                                                } else {
1518                                                        AlternativeFinder finder( indexer, env );
1519                                                        finder.find( attrExpr->get_expr() );
1520                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1521                                                                if ( choice->expr->get_result()->size() == 1 ) {
1522                                                                        resolveAttr(data, function, choice->expr->get_result(), choice->env, altFinder );
1523                                                                } // fi
1524                                                        } // for
1525                                                } // if
1526                                        } // if
1527                                } // if
1528                        } // for
1529                } else {
1530                        for ( auto & data : attrList ) {
1531                                Cost cost = Cost::zero;
1532                                Expression * newExpr = data.combine( cost );
1533                                alternatives.push_back( Alternative( newExpr, env, Cost::zero, cost ) );
1534                                renameTypes( alternatives.back().expr );
1535                        } // for
1536                } // if
1537        }
1538
1539        void AlternativeFinder::Finder::postvisit( LogicalExpr *logicalExpr ) {
1540                AlternativeFinder firstFinder( indexer, env );
1541                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1542                if ( firstFinder.alternatives.empty() ) return;
1543                AlternativeFinder secondFinder( indexer, env );
1544                secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1545                if ( secondFinder.alternatives.empty() ) return;
1546                for ( const Alternative & first : firstFinder.alternatives ) {
1547                        for ( const Alternative & second : secondFinder.alternatives ) {
1548                                TypeEnvironment compositeEnv;
1549                                compositeEnv.simpleCombine( first.env );
1550                                compositeEnv.simpleCombine( second.env );
1551
1552                                LogicalExpr *newExpr = new LogicalExpr( first.expr->clone(), second.expr->clone(), logicalExpr->get_isAnd() );
1553                                alternatives.push_back( Alternative( newExpr, compositeEnv, first.cost + second.cost ) );
1554                        }
1555                }
1556        }
1557
1558        void AlternativeFinder::Finder::postvisit( ConditionalExpr *conditionalExpr ) {
1559                // find alternatives for condition
1560                AlternativeFinder firstFinder( indexer, env );
1561                firstFinder.findWithAdjustment( conditionalExpr->arg1 );
1562                if ( firstFinder.alternatives.empty() ) return;
1563                // find alternatives for true expression
1564                AlternativeFinder secondFinder( indexer, env );
1565                secondFinder.findWithAdjustment( conditionalExpr->arg2 );
1566                if ( secondFinder.alternatives.empty() ) return;
1567                // find alterantives for false expression
1568                AlternativeFinder thirdFinder( indexer, env );
1569                thirdFinder.findWithAdjustment( conditionalExpr->arg3 );
1570                if ( thirdFinder.alternatives.empty() ) return;
1571                for ( const Alternative & first : firstFinder.alternatives ) {
1572                        for ( const Alternative & second : secondFinder.alternatives ) {
1573                                for ( const Alternative & third : thirdFinder.alternatives ) {
1574                                        TypeEnvironment compositeEnv;
1575                                        compositeEnv.simpleCombine( first.env );
1576                                        compositeEnv.simpleCombine( second.env );
1577                                        compositeEnv.simpleCombine( third.env );
1578
1579                                        // unify true and false types, then infer parameters to produce new alternatives
1580                                        OpenVarSet openVars;
1581                                        AssertionSet needAssertions, haveAssertions;
1582                                        Alternative newAlt( 0, compositeEnv, first.cost + second.cost + third.cost );
1583                                        Type* commonType = nullptr;
1584                                        if ( unify( second.expr->result, third.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1585                                                ConditionalExpr *newExpr = new ConditionalExpr( first.expr->clone(), second.expr->clone(), third.expr->clone() );
1586                                                newExpr->result = commonType ? commonType : second.expr->result->clone();
1587                                                // convert both options to the conditional result type
1588                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1589                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1590                                                newAlt.expr = newExpr;
1591                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1592                                        } // if
1593                                } // for
1594                        } // for
1595                } // for
1596        }
1597
1598        void AlternativeFinder::Finder::postvisit( CommaExpr *commaExpr ) {
1599                TypeEnvironment newEnv( env );
1600                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1601                AlternativeFinder secondFinder( indexer, newEnv );
1602                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1603                for ( const Alternative & alt : secondFinder.alternatives ) {
1604                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt.expr->clone() ), alt.env, alt.cost ) );
1605                } // for
1606                delete newFirstArg;
1607        }
1608
1609        void AlternativeFinder::Finder::postvisit( RangeExpr * rangeExpr ) {
1610                // resolve low and high, accept alternatives whose low and high types unify
1611                AlternativeFinder firstFinder( indexer, env );
1612                firstFinder.findWithAdjustment( rangeExpr->low );
1613                if ( firstFinder.alternatives.empty() ) return;
1614                AlternativeFinder secondFinder( indexer, env );
1615                secondFinder.findWithAdjustment( rangeExpr->high );
1616                if ( secondFinder.alternatives.empty() ) return;
1617                for ( const Alternative & first : firstFinder.alternatives ) {
1618                        for ( const Alternative & second : secondFinder.alternatives ) {
1619                                TypeEnvironment compositeEnv;
1620                                compositeEnv.simpleCombine( first.env );
1621                                compositeEnv.simpleCombine( second.env );
1622                                OpenVarSet openVars;
1623                                AssertionSet needAssertions, haveAssertions;
1624                                Alternative newAlt( 0, compositeEnv, first.cost + second.cost );
1625                                Type* commonType = nullptr;
1626                                if ( unify( first.expr->result, second.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1627                                        RangeExpr * newExpr = new RangeExpr( first.expr->clone(), second.expr->clone() );
1628                                        newExpr->result = commonType ? commonType : first.expr->result->clone();
1629                                        newAlt.expr = newExpr;
1630                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1631                                } // if
1632                        } // for
1633                } // for
1634        }
1635
1636        void AlternativeFinder::Finder::postvisit( UntypedTupleExpr *tupleExpr ) {
1637                std::vector< AlternativeFinder > subExprAlternatives;
1638                altFinder.findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
1639                        back_inserter( subExprAlternatives ) );
1640                std::vector< AltList > possibilities;
1641                combos( subExprAlternatives.begin(), subExprAlternatives.end(),
1642                        back_inserter( possibilities ) );
1643                for ( const AltList& alts : possibilities ) {
1644                        std::list< Expression * > exprs;
1645                        makeExprList( alts, exprs );
1646
1647                        TypeEnvironment compositeEnv;
1648                        simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
1649                        alternatives.push_back(
1650                                Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
1651                } // for
1652        }
1653
1654        void AlternativeFinder::Finder::postvisit( TupleExpr *tupleExpr ) {
1655                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1656        }
1657
1658        void AlternativeFinder::Finder::postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1659                alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1660        }
1661
1662        void AlternativeFinder::Finder::postvisit( ConstructorExpr * ctorExpr ) {
1663                AlternativeFinder finder( indexer, env );
1664                // don't prune here, since it's guaranteed all alternatives will have the same type
1665                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1666                finder.findWithoutPrune( ctorExpr->get_callExpr() );
1667                for ( Alternative & alt : finder.alternatives ) {
1668                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1669                }
1670        }
1671
1672        void AlternativeFinder::Finder::postvisit( TupleIndexExpr *tupleExpr ) {
1673                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1674        }
1675
1676        void AlternativeFinder::Finder::postvisit( TupleAssignExpr *tupleAssignExpr ) {
1677                alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1678        }
1679
1680        void AlternativeFinder::Finder::postvisit( UniqueExpr *unqExpr ) {
1681                AlternativeFinder finder( indexer, env );
1682                finder.findWithAdjustment( unqExpr->get_expr() );
1683                for ( Alternative & alt : finder.alternatives ) {
1684                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1685                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1686                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1687                }
1688        }
1689
1690        void AlternativeFinder::Finder::postvisit( StmtExpr *stmtExpr ) {
1691                StmtExpr * newStmtExpr = stmtExpr->clone();
1692                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1693                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1694                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1695        }
1696
1697        void AlternativeFinder::Finder::postvisit( UntypedInitExpr *initExpr ) {
1698                // handle each option like a cast
1699                AltList candidates;
1700                PRINT(
1701                        std::cerr << "untyped init expr: " << initExpr << std::endl;
1702                )
1703                // O(N^2) checks of d-types with e-types
1704                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1705                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
1706                        SymTab::validateType( toType, &indexer );
1707                        adjustExprType( toType, env, indexer );
1708                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1709                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1710                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1711                        AlternativeFinder finder( indexer, env );
1712                        finder.targetType = toType;
1713                        finder.findWithAdjustment( initExpr->expr );
1714                        for ( Alternative & alt : finder.get_alternatives() ) {
1715                                TypeEnvironment newEnv( alt.env );
1716                                AssertionSet needAssertions, haveAssertions;
1717                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
1718                                PRINT(
1719                                        std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl;
1720                                )
1721                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1722                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1723                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1724                                // to.
1725                                int discardedValues = alt.expr->result->size() - toType->size();
1726                                if ( discardedValues < 0 ) continue;
1727                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1728                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1729                                // unification run for side-effects
1730                                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??
1731
1732                                Cost thisCost = castCost( alt.expr->result, toType, indexer, newEnv );
1733                                if ( thisCost != Cost::infinity ) {
1734                                        // count one safe conversion for each value that is thrown away
1735                                        thisCost.incSafe( discardedValues );
1736                                        Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType, true ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost );
1737                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
1738                                }
1739                        }
1740                }
1741
1742                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1743                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1744                // selects first based on argument cost, then on conversion cost.
1745                AltList minArgCost;
1746                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1747                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1748        }
1749
1750        void AlternativeFinder::Finder::postvisit( InitExpr * ) {
1751                assertf( false, "AlternativeFinder should never see a resolved InitExpr." );
1752        }
1753
1754        void AlternativeFinder::Finder::postvisit( DeletedExpr * ) {
1755                assertf( false, "AlternativeFinder should never see a DeletedExpr." );
1756        }
1757
1758        void AlternativeFinder::Finder::postvisit( GenericExpr * ) {
1759                assertf( false, "_Generic is not yet supported." );
1760        }
1761} // namespace ResolvExpr
1762
1763// Local Variables: //
1764// tab-width: 4 //
1765// mode: c++ //
1766// compile-command: "make install" //
1767// End: //
Note: See TracBrowser for help on using the repository browser.