source: src/ResolvExpr/AlternativeFinder.cc @ 1db306a

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 1db306a was 1db306a, checked in by Thierry Delisle <tdelisle@…>, 2 years ago

First attempt to sort alternatives before printing.

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