source: src/ResolvExpr/AlternativeFinder.cc @ 6d6e829

aaron-thesisarm-ehcleanup-dtorsdeferred_resnjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexer
Last change on this file since 6d6e829 was 6d6e829, checked in by Aaron Moss <a3moss@…>, 3 years ago

First compiling draft of deferred assertions (build failure)

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