source: src/ResolvExpr/AlternativeFinder.cc @ df626eb

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since df626eb was df626eb, checked in by Rob Schluntz <rschlunt@…>, 6 years ago

Move inferred parameters to Exception base class

  • Property mode set to 100644
File size: 60.8 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// AlternativeFinder.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Sat May 16 23:52:08 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Mon Aug 28 13:47:24 2017
13// Update Count     : 32
14//
15
16#include <algorithm>               // for copy
17#include <cassert>                 // for strict_dynamic_cast, assert, assertf
18#include <iostream>                // for operator<<, cerr, ostream, endl
19#include <iterator>                // for back_insert_iterator, back_inserter
20#include <list>                    // for _List_iterator, list, _List_const_...
21#include <map>                     // for _Rb_tree_iterator, map, _Rb_tree_c...
22#include <memory>                  // for allocator_traits<>::value_type
23#include <utility>                 // for pair
24
25#include "Alternative.h"           // for AltList, Alternative
26#include "AlternativeFinder.h"
27#include "Common/SemanticError.h"  // for SemanticError
28#include "Common/utility.h"        // for deleteAll, printAll, CodeLocation
29#include "Cost.h"                  // for Cost, Cost::zero, operator<<, Cost...
30#include "InitTweak/InitTweak.h"   // for getFunctionName
31#include "RenameVars.h"            // for RenameVars, global_renamer
32#include "ResolveTypeof.h"         // for resolveTypeof
33#include "Resolver.h"              // for resolveStmtExpr
34#include "SymTab/Indexer.h"        // for Indexer
35#include "SymTab/Mangler.h"        // for Mangler
36#include "SymTab/Validate.h"       // for validateType
37#include "SynTree/Constant.h"      // for Constant
38#include "SynTree/Declaration.h"   // for DeclarationWithType, TypeDecl, Dec...
39#include "SynTree/Expression.h"    // for Expression, CastExpr, NameExpr
40#include "SynTree/Initializer.h"   // for SingleInit, operator<<, Designation
41#include "SynTree/SynTree.h"       // for UniqueId
42#include "SynTree/Type.h"          // for Type, FunctionType, PointerType
43#include "Tuples/Explode.h"        // for explode
44#include "Tuples/Tuples.h"         // for isTtype, handleTupleAssignment
45#include "Unify.h"                 // for unify
46#include "typeops.h"               // for adjustExprType, polyCost, castCost
47
48extern bool resolvep;
49#define PRINT( text ) if ( resolvep ) { text }
50//#define DEBUG_COST
51
52namespace ResolvExpr {
53        Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) {
54                CastExpr *castToVoid = new CastExpr( expr );
55
56                AlternativeFinder finder( indexer, env );
57                finder.findWithAdjustment( castToVoid );
58
59                // it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0
60                // interpretations, an exception has already been thrown.
61                assert( finder.get_alternatives().size() == 1 );
62                CastExpr *newExpr = dynamic_cast< CastExpr* >( finder.get_alternatives().front().expr );
63                assert( newExpr );
64                env = finder.get_alternatives().front().env;
65                return newExpr->get_arg()->clone();
66        }
67
68        Cost sumCost( const AltList &in ) {
69                Cost total = Cost::zero;
70                for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
71                        total += i->cost;
72                }
73                return total;
74        }
75
76        namespace {
77                void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt = 0 ) {
78                        Indenter indent = { Indenter::tabsize, indentAmt };
79                        for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
80                                i->print( os, indent );
81                                os << std::endl;
82                        }
83                }
84
85                void makeExprList( const AltList &in, std::list< Expression* > &out ) {
86                        for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
87                                out.push_back( i->expr->clone() );
88                        }
89                }
90
91                struct PruneStruct {
92                        bool isAmbiguous;
93                        AltList::iterator candidate;
94                        PruneStruct() {}
95                        PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
96                };
97
98                /// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
99                template< typename InputIterator, typename OutputIterator >
100                void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out ) {
101                        // select the alternatives that have the minimum conversion cost for a particular set of result types
102                        std::map< std::string, PruneStruct > selected;
103                        for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
104                                PruneStruct current( candidate );
105                                std::string mangleName;
106                                {
107                                        Type * newType = candidate->expr->get_result()->clone();
108                                        candidate->env.apply( newType );
109                                        mangleName = SymTab::Mangler::mangle( newType );
110                                        delete newType;
111                                }
112                                std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
113                                if ( mapPlace != selected.end() ) {
114                                        if ( candidate->cost < mapPlace->second.candidate->cost ) {
115                                                PRINT(
116                                                        std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
117                                                )
118                                                selected[ mangleName ] = current;
119                                        } else if ( candidate->cost == mapPlace->second.candidate->cost ) {
120                                                PRINT(
121                                                        std::cerr << "marking ambiguous" << std::endl;
122                                                )
123                                                mapPlace->second.isAmbiguous = true;
124                                        }
125                                } else {
126                                        selected[ mangleName ] = current;
127                                }
128                        }
129
130                        PRINT(
131                                std::cerr << "there are " << selected.size() << " alternatives before elimination" << std::endl;
132                        )
133
134                        // accept the alternatives that were unambiguous
135                        for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
136                                if ( ! target->second.isAmbiguous ) {
137                                        Alternative &alt = *target->second.candidate;
138                                        alt.env.applyFree( alt.expr->get_result() );
139                                        *out++ = alt;
140                                }
141                        }
142                }
143
144                void renameTypes( Expression *expr ) {
145                        expr->get_result()->accept( global_renamer );
146                }
147        } // namespace
148
149        void referenceToRvalueConversion( Expression *& expr ) {
150                if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
151                        // cast away reference from expr
152                        expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() );
153                }
154        }
155
156        template< typename InputIterator, typename OutputIterator >
157        void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
158                while ( begin != end ) {
159                        AlternativeFinder finder( indexer, env );
160                        finder.findWithAdjustment( *begin );
161                        // XXX  either this
162                        //Designators::fixDesignations( finder, (*begin++)->get_argName() );
163                        // or XXX this
164                        begin++;
165                        PRINT(
166                                std::cerr << "findSubExprs" << std::endl;
167                                printAlts( finder.alternatives, std::cerr );
168                        )
169                        *out++ = finder;
170                }
171        }
172
173        AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
174                : indexer( indexer ), env( env ) {
175        }
176
177        void AlternativeFinder::find( Expression *expr, bool adjust, bool prune, bool failFast ) {
178                expr->accept( *this );
179                if ( failFast && alternatives.empty() ) {
180                        throw SemanticError( "No reasonable alternatives for expression ", expr );
181                }
182                if ( prune ) {
183                        PRINT(
184                                std::cerr << "alternatives before prune:" << std::endl;
185                                printAlts( alternatives, std::cerr );
186                        )
187                        AltList::iterator oldBegin = alternatives.begin();
188                        pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) );
189                        if ( failFast && alternatives.begin() == oldBegin ) {
190                                std::ostringstream stream;
191                                AltList winners;
192                                findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
193                                stream << "Cannot choose between " << winners.size() << " alternatives for expression\n";
194                                expr->print( stream );
195                                stream << "Alternatives are:\n";
196                                printAlts( winners, stream, 1 );
197                                throw SemanticError( stream.str() );
198                        }
199                        alternatives.erase( oldBegin, alternatives.end() );
200                        PRINT(
201                                std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
202                        )
203                }
204                // adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted
205                for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
206                        if ( adjust ) {
207                                adjustExprType( i->expr->get_result(), i->env, indexer );
208                        }
209                }
210
211                // Central location to handle gcc extension keyword, etc. for all expression types.
212                for ( Alternative &iter: alternatives ) {
213                        iter.expr->set_extension( expr->get_extension() );
214                        iter.expr->location = expr->location;
215                } // for
216        }
217
218        void AlternativeFinder::findWithAdjustment( Expression *expr ) {
219                find( expr, true );
220        }
221
222        void AlternativeFinder::findWithoutPrune( Expression * expr ) {
223                find( expr, true, false );
224        }
225
226        void AlternativeFinder::maybeFind( Expression * expr ) {
227                find( expr, true, true, false );
228        }
229
230        void AlternativeFinder::addAnonConversions( const Alternative & alt ) {
231                // adds anonymous member interpretations whenever an aggregate value type is seen.
232                // 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
233                std::unique_ptr<Expression> aggrExpr( alt.expr->clone() );
234                alt.env.apply( aggrExpr->get_result() );
235                Type * aggrType = aggrExpr->get_result();
236                if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
237                        aggrType = aggrType->stripReferences();
238                        aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
239                }
240
241                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
242                        NameExpr nameExpr( "" );
243                        addAggMembers( structInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
244                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
245                        NameExpr nameExpr( "" );
246                        addAggMembers( unionInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
247                } // if
248        }
249
250        template< typename StructOrUnionType >
251        void AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
252                // by this point, member must be a name expr
253                NameExpr * nameExpr = dynamic_cast< NameExpr * >( member );
254                if ( ! nameExpr ) return;
255                const std::string & name = nameExpr->get_name();
256                std::list< Declaration* > members;
257                aggInst->lookup( name, members );
258
259                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
260                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
261                                alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
262                                renameTypes( alternatives.back().expr );
263                                addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
264                        } else {
265                                assert( false );
266                        }
267                }
268        }
269
270        void AlternativeFinder::addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
271                if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
272                        // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
273                        // xxx - this should be improved by memoizing the value of constant exprs
274                        // during parsing and reusing that information here.
275                        std::stringstream ss( constantExpr->get_constant()->get_value() );
276                        int val = 0;
277                        std::string tmp;
278                        if ( ss >> val && ! (ss >> tmp) ) {
279                                if ( val >= 0 && (unsigned int)val < tupleType->size() ) {
280                                        alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
281                                } // if
282                        } // if
283                } else if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( member ) ) {
284                        // xxx - temporary hack until 0/1 are int constants
285                        if ( nameExpr->get_name() == "0" || nameExpr->get_name() == "1" ) {
286                                std::stringstream ss( nameExpr->get_name() );
287                                int val;
288                                ss >> val;
289                                alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
290                        }
291                } // if
292        }
293
294        void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
295                alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
296        }
297
298        Cost computeConversionCost( Type * actualType, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
299                PRINT(
300                        std::cerr << std::endl << "converting ";
301                        actualType->print( std::cerr, 8 );
302                        std::cerr << std::endl << " to ";
303                        formalType->print( std::cerr, 8 );
304                        std::cerr << std::endl << "environment is: ";
305                        env.print( std::cerr, 8 );
306                        std::cerr << std::endl;
307                )
308                Cost convCost = conversionCost( actualType, formalType, indexer, env );
309                PRINT(
310                        std::cerr << std::endl << "cost is" << convCost << std::endl;
311                )
312                if ( convCost == Cost::infinity ) {
313                        return convCost;
314                }
315                convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) );
316                return convCost;
317        }
318
319        Cost computeExpressionConversionCost( Expression *& actualExpr, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
320                Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env );
321                // if ( convCost != Cost::zero ) {
322
323                // xxx - temporary -- ignore poly cost, since this causes some polymorphic functions to be cast, which causes the specialize
324                // pass to try to specialize them, which currently does not work. Once that is fixed, remove the next 3 lines and uncomment the
325                // previous line.
326                Cost tmpCost = convCost;
327                tmpCost.incPoly( -tmpCost.get_polyCost() );
328                if ( tmpCost != Cost::zero ) {
329                        Type *newType = formalType->clone();
330                        env.apply( newType );
331                        actualExpr = new CastExpr( actualExpr, newType );
332                        // 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
333                        // inconsistent, once this is fixed it should be possible to resolve the cast.
334                        // 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.
335
336                        // AlternativeFinder finder( indexer, env );
337                        // finder.findWithAdjustment( actualExpr );
338                        // assertf( finder.get_alternatives().size() > 0, "Somehow castable expression failed to find alternatives." );
339                        // assertf( finder.get_alternatives().size() == 1, "Somehow got multiple alternatives for known cast expression." );
340                        // Alternative & alt = finder.get_alternatives().front();
341                        // delete actualExpr;
342                        // actualExpr = alt.expr->clone();
343                }
344                return convCost;
345        }
346
347        Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
348                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( alt.expr );
349                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
350                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
351
352                Cost convCost = Cost::zero;
353                std::list< DeclarationWithType* >& formals = function->get_parameters();
354                std::list< DeclarationWithType* >::iterator formal = formals.begin();
355                std::list< Expression* >& actuals = appExpr->get_args();
356
357                for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
358                        Type * actualType = (*actualExpr)->get_result();
359                        PRINT(
360                                std::cerr << "actual expression:" << std::endl;
361                                (*actualExpr)->print( std::cerr, 8 );
362                                std::cerr << "--- results are" << std::endl;
363                                actualType->print( std::cerr, 8 );
364                        )
365                        if ( formal == formals.end() ) {
366                                if ( function->get_isVarArgs() ) {
367                                        convCost.incUnsafe();
368                                        // convert reference-typed expressions to value-typed expressions
369                                        referenceToRvalueConversion( *actualExpr );
370                                        continue;
371                                } else {
372                                        return Cost::infinity;
373                                }
374                        }
375                        Type * formalType = (*formal)->get_type();
376                        PRINT(
377                                std::cerr << std::endl << "converting ";
378                                actualType->print( std::cerr, 8 );
379                                std::cerr << std::endl << " to ";
380                                formalType->print( std::cerr, 8 );
381                                std::cerr << std::endl << "environment is: ";
382                                alt.env.print( std::cerr, 8 );
383                                std::cerr << std::endl;
384                        )
385                        convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
386                        ++formal; // can't be in for-loop update because of the continue
387                }
388                if ( formal != formals.end() ) {
389                        return Cost::infinity;
390                }
391
392                for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
393                        convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
394                }
395
396                return convCost;
397        }
398
399        /// Adds type variables to the open variable set and marks their assertions
400        void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
401                for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
402                        unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar };
403                        for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
404                                needAssertions[ *assert ].isUsed = true;
405                        }
406///     needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
407                }
408        }
409
410        /// instantiate a single argument by matching actuals from [actualIt, actualEnd) against formalType,
411        /// producing expression(s) in out and their total cost in cost.
412        template< typename AltIterator, typename OutputIterator >
413        bool instantiateArgument( Type * formalType, Initializer * defaultValue, AltIterator & actualIt, AltIterator actualEnd, OpenVarSet & openVars, TypeEnvironment & resultEnv, AssertionSet & resultNeed, AssertionSet & resultHave, const SymTab::Indexer & indexer, Cost & cost, OutputIterator out ) {
414                if ( TupleType * tupleType = dynamic_cast< TupleType * >( formalType ) ) {
415                        // formalType is a TupleType - group actuals into a TupleExpr whose type unifies with the TupleType
416                        std::list< Expression * > exprs;
417                        for ( Type * type : *tupleType ) {
418                                if ( ! instantiateArgument( type, defaultValue, actualIt, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( exprs ) ) ) {
419                                        deleteAll( exprs );
420                                        return false;
421                                }
422                        }
423                        *out++ = new TupleExpr( exprs );
424                } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
425                        // xxx - mixing default arguments with variadic??
426                        std::list< Expression * > exprs;
427                        for ( ; actualIt != actualEnd; ++actualIt ) {
428                                exprs.push_back( actualIt->expr->clone() );
429                                cost += actualIt->cost;
430                        }
431                        Expression * arg = nullptr;
432                        if ( exprs.size() == 1 && Tuples::isTtype( exprs.front()->get_result() ) ) {
433                                // the case where a ttype value is passed directly is special, e.g. for argument forwarding purposes
434                                // xxx - what if passing multiple arguments, last of which is ttype?
435                                // xxx - what would happen if unify was changed so that unifying tuple types flattened both before unifying lists? then pass in TupleType(ttype) below.
436                                arg = exprs.front();
437                        } else {
438                                arg = new TupleExpr( exprs );
439                        }
440                        assert( arg && arg->get_result() );
441                        if ( ! unify( ttype, arg->get_result(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
442                                return false;
443                        }
444                        *out++ = arg;
445                } else if ( actualIt != actualEnd ) {
446                        // both actualType and formalType are atomic (non-tuple) types - if they unify
447                        // then accept actual as an argument, otherwise return false (fail to instantiate argument)
448                        Expression * actual = actualIt->expr;
449                        Type * actualType = actual->get_result();
450
451                        PRINT(
452                                std::cerr << "formal type is ";
453                                formalType->print( std::cerr );
454                                std::cerr << std::endl << "actual type is ";
455                                actualType->print( std::cerr );
456                                std::cerr << std::endl;
457                        )
458                        if ( ! unify( formalType, actualType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
459                                // std::cerr << "unify failed" << std::endl;
460                                return false;
461                        }
462                        // move the expression from the alternative to the output iterator
463                        *out++ = actual;
464                        actualIt->expr = nullptr;
465                        cost += actualIt->cost;
466                        ++actualIt;
467                } else {
468                        // End of actuals - Handle default values
469                        if ( SingleInit *si = dynamic_cast<SingleInit *>( defaultValue )) {
470                                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( si->get_value() ) ) {
471                                        // so far, only constant expressions are accepted as default values
472                                        if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( castExpr->get_arg() ) ) {
473                                                if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) ) {
474                                                        if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
475                                                                *out++ = cnstexpr->clone();
476                                                                return true;
477                                                        } // if
478                                                } // if
479                                        } // if
480                                }
481                        } // if
482                        return false;
483                } // if
484                return true;
485        }
486
487        bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) {
488                simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
489                // make sure we don't widen any existing bindings
490                for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) {
491                        i->allowWidening = false;
492                }
493                resultEnv.extractOpenVars( openVars );
494
495                // flatten actuals so that each actual has an atomic (non-tuple) type
496                AltList exploded;
497                Tuples::explode( actuals, indexer, back_inserter( exploded ) );
498
499                AltList::iterator actualExpr = exploded.begin();
500                AltList::iterator actualEnd = exploded.end();
501                for ( DeclarationWithType * formal : formals ) {
502                        // match flattened actuals with formal parameters - actuals will be grouped to match
503                        // with formals as appropriate
504                        Cost cost = Cost::zero;
505                        std::list< Expression * > newExprs;
506                        ObjectDecl * obj = strict_dynamic_cast< ObjectDecl * >( formal );
507                        if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) {
508                                deleteAll( newExprs );
509                                return false;
510                        }
511                        // success - produce argument as a new alternative
512                        assert( newExprs.size() == 1 );
513                        out.push_back( Alternative( newExprs.front(), resultEnv, cost ) );
514                }
515                if ( actualExpr != actualEnd ) {
516                        // there are still actuals remaining, but we've run out of formal parameters to match against
517                        // this is okay only if the function is variadic
518                        if ( ! isVarArgs ) {
519                                return false;
520                        }
521                        out.splice( out.end(), exploded, actualExpr, actualEnd );
522                }
523                return true;
524        }
525
526        // /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
527        //typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;
528
529        static const int recursionLimit = /*10*/ 4;  ///< Limit to depth of recursion satisfaction
530        //static const unsigned recursionParentLimit = 1;  ///< Limit to the number of times an assertion can recursively use itself
531
532        void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
533                for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
534                        if ( i->second.isUsed ) {
535                                indexer.addId( i->first );
536                        }
537                }
538        }
539
540        template< typename ForwardIterator, typename OutputIterator >
541        void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /*const AssertionParentSet &needParents,*/
542                                                 int level, const SymTab::Indexer &indexer, OutputIterator out ) {
543                if ( begin == end ) {
544                        if ( newNeed.empty() ) {
545                                PRINT(
546                                        std::cerr << "all assertions satisfied, output alternative: ";
547                                        newAlt.print( std::cerr );
548                                        std::cerr << std::endl;
549                                );
550                                *out++ = newAlt;
551                                return;
552                        } else if ( level >= recursionLimit ) {
553                                throw SemanticError( "Too many recursive assertions" );
554                        } else {
555                                AssertionSet newerNeed;
556                                PRINT(
557                                        std::cerr << "recursing with new set:" << std::endl;
558                                        printAssertionSet( newNeed, std::cerr, 8 );
559                                )
560                                inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /*needParents,*/ level+1, indexer, out );
561                                return;
562                        }
563                }
564
565                ForwardIterator cur = begin++;
566                if ( ! cur->second.isUsed ) {
567                        inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /*needParents,*/ level, indexer, out );
568                        return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
569                }
570                DeclarationWithType *curDecl = cur->first;
571
572                PRINT(
573                        std::cerr << "inferRecursive: assertion is ";
574                        curDecl->print( std::cerr );
575                        std::cerr << std::endl;
576                )
577                std::list< DeclarationWithType* > candidates;
578                decls.lookupId( curDecl->get_name(), candidates );
579///   if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
580                for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {
581                        PRINT(
582                                std::cerr << "inferRecursive: candidate is ";
583                                (*candidate)->print( std::cerr );
584                                std::cerr << std::endl;
585                        )
586
587                        AssertionSet newHave, newerNeed( newNeed );
588                        TypeEnvironment newEnv( newAlt.env );
589                        OpenVarSet newOpenVars( openVars );
590                        Type *adjType = (*candidate)->get_type()->clone();
591                        adjustExprType( adjType, newEnv, indexer );
592                        adjType->accept( global_renamer );
593                        PRINT(
594                                std::cerr << "unifying ";
595                                curDecl->get_type()->print( std::cerr );
596                                std::cerr << " with ";
597                                adjType->print( std::cerr );
598                                std::cerr << std::endl;
599                        )
600                        if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
601                                PRINT(
602                                        std::cerr << "success!" << std::endl;
603                                )
604                                SymTab::Indexer newDecls( decls );
605                                addToIndexer( newHave, newDecls );
606                                Alternative newerAlt( newAlt );
607                                newerAlt.env = newEnv;
608                                assertf( (*candidate)->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( *candidate ).c_str() );
609                                DeclarationWithType *candDecl = static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );
610
611                                // everything with an empty idChain was pulled in by the current assertion.
612                                // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
613                                for ( auto & a : newerNeed ) {
614                                        if ( a.second.idChain.empty() ) {
615                                                a.second.idChain = cur->second.idChain;
616                                                a.second.idChain.push_back( curDecl->get_uniqueId() );
617                                        }
618                                }
619
620                                //AssertionParentSet newNeedParents( needParents );
621                                // skip repeatingly-self-recursive assertion satisfaction
622                                // DOESN'T WORK: grandchild nodes conflict with their cousins
623                                //if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
624                                Expression *varExpr = new VariableExpr( candDecl );
625                                delete varExpr->get_result();
626                                varExpr->set_result( adjType->clone() );
627                                PRINT(
628                                        std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
629                                        curDecl->print( std::cerr );
630                                        std::cerr << " with declaration " << (*candidate)->get_uniqueId() << " ";
631                                        (*candidate)->print( std::cerr );
632                                        std::cerr << std::endl;
633                                )
634                                // 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).
635                                InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
636                                for ( UniqueId id : cur->second.idChain ) {
637                                        inferParameters = (*inferParameters)[ id ].inferParams.get();
638                                }
639                                // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
640                                (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
641                                inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /*newNeedParents,*/ level, indexer, out );
642                        } else {
643                                delete adjType;
644                        }
645                }
646        }
647
648        template< typename OutputIterator >
649        void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
650//      PRINT(
651//          std::cerr << "inferParameters: assertions needed are" << std::endl;
652//          printAll( need, std::cerr, 8 );
653//          )
654                SymTab::Indexer decls( indexer );
655                // PRINT(
656                //      std::cerr << "============= original indexer" << std::endl;
657                //      indexer.print( std::cerr );
658                //      std::cerr << "============= new indexer" << std::endl;
659                //      decls.print( std::cerr );
660                // )
661                addToIndexer( have, decls );
662                AssertionSet newNeed;
663                //AssertionParentSet needParents;
664                PRINT(
665                        std::cerr << "env is: " << std::endl;
666                        newAlt.env.print( std::cerr, 0 );
667                        std::cerr << std::endl;
668                )
669
670                inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /*needParents,*/ 0, indexer, out );
671//      PRINT(
672//          std::cerr << "declaration 14 is ";
673//          Declaration::declFromId
674//          *out++ = newAlt;
675//          )
676        }
677
678        template< typename OutputIterator >
679        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) {
680                OpenVarSet openVars;
681                AssertionSet resultNeed, resultHave;
682                TypeEnvironment resultEnv;
683                makeUnifiableVars( funcType, openVars, resultNeed );
684                resultEnv.add( funcType->get_forall() ); // add all type variables as open variables now so that those not used in the parameter list are still considered open
685                AltList instantiatedActuals; // filled by instantiate function
686                if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
687                        // attempt to narrow based on expected target type
688                        Type * returnType = funcType->get_returnVals().front()->get_type();
689                        if ( ! unify( returnType, targetType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
690                                // unification failed, don't pursue this alternative
691                                return;
692                        }
693                }
694
695                if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) {
696                        ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
697                        Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) );
698                        makeExprList( instantiatedActuals, appExpr->get_args() );
699                        PRINT(
700                                std::cerr << "instantiate function success: " << appExpr << std::endl;
701                                std::cerr << "need assertions:" << std::endl;
702                                printAssertionSet( resultNeed, std::cerr, 8 );
703                        )
704                        inferParameters( resultNeed, resultHave, newAlt, openVars, out );
705                }
706        }
707
708        void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
709                AlternativeFinder funcFinder( indexer, env );
710                funcFinder.findWithAdjustment( untypedExpr->get_function() );
711                // if there are no function alternatives, then proceeding is a waste of time.
712                if ( funcFinder.alternatives.empty() ) return;
713
714                std::list< AlternativeFinder > argAlternatives;
715                findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );
716
717                std::list< AltList > possibilities;
718                combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
719
720                // take care of possible tuple assignments
721                // if not tuple assignment, assignment is taken care of as a normal function call
722                Tuples::handleTupleAssignment( *this, untypedExpr, possibilities );
723
724                // find function operators
725                static NameExpr *opExpr = new NameExpr( "?()" );
726                AlternativeFinder funcOpFinder( indexer, env );
727                // it's ok if there aren't any defined function ops
728                funcOpFinder.maybeFind( opExpr);
729                PRINT(
730                        std::cerr << "known function ops:" << std::endl;
731                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
732                )
733
734                AltList candidates;
735                SemanticError errors;
736                for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
737                        try {
738                                PRINT(
739                                        std::cerr << "working on alternative: " << std::endl;
740                                        func->print( std::cerr, 8 );
741                                )
742                                // check if the type is pointer to function
743                                if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->get_result()->stripReferences() ) ) {
744                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
745                                                Alternative newFunc( *func );
746                                                referenceToRvalueConversion( newFunc.expr );
747                                                for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
748                                                        // XXX
749                                                        //Designators::check_alternative( function, *actualAlt );
750                                                        makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) );
751                                                }
752                                        }
753                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
754                                        EqvClass eqvClass;
755                                        if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
756                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
757                                                        Alternative newFunc( *func );
758                                                        referenceToRvalueConversion( newFunc.expr );
759                                                        for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
760                                                                makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) );
761                                                        } // for
762                                                } // if
763                                        } // if
764                                }
765
766                                // try each function operator ?() with the current function alternative and each of the argument combinations
767                                for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
768                                        // check if the type is pointer to function
769                                        if ( PointerType *pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result()->stripReferences() ) ) {
770                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
771                                                        Alternative newFunc( *funcOp );
772                                                        referenceToRvalueConversion( newFunc.expr );
773                                                        for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
774                                                                AltList currentAlt;
775                                                                currentAlt.push_back( *func );
776                                                                currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
777                                                                makeFunctionAlternatives( newFunc, function, currentAlt, std::back_inserter( candidates ) );
778                                                        } // for
779                                                } // if
780                                        } // if
781                                } // for
782                        } catch ( SemanticError &e ) {
783                                errors.append( e );
784                        }
785                } // for
786
787                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
788                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
789
790                // compute conversionsion costs
791                for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
792                        Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer );
793
794                        PRINT(
795                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc->expr );
796                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
797                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
798                                std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
799                                std::cerr << "formals are:" << std::endl;
800                                printAll( function->get_parameters(), std::cerr, 8 );
801                                std::cerr << "actuals are:" << std::endl;
802                                printAll( appExpr->get_args(), std::cerr, 8 );
803                                std::cerr << "bindings are:" << std::endl;
804                                withFunc->env.print( std::cerr, 8 );
805                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
806                        )
807                        if ( cvtCost != Cost::infinity ) {
808                                withFunc->cvtCost = cvtCost;
809                                alternatives.push_back( *withFunc );
810                        } // if
811                } // for
812
813                candidates.clear();
814                candidates.splice( candidates.end(), alternatives );
815
816                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
817
818                // function may return struct or union value, in which case we need to add alternatives for implicit
819                // conversions to each of the anonymous members, must happen after findMinCost since anon conversions
820                // are never the cheapest expression
821                for ( const Alternative & alt : alternatives ) {
822                        addAnonConversions( alt );
823                }
824
825                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
826                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
827                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
828                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
829                        //   const char * x = "hello world";
830                        //   unsigned char ch = x[0];
831                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
832                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
833                        // fix this issue in a more robust way.
834                        targetType = nullptr;
835                        visit( untypedExpr );
836                }
837        }
838
839        bool isLvalue( Expression *expr ) {
840                // xxx - recurse into tuples?
841                return expr->result && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
842        }
843
844        void AlternativeFinder::visit( AddressExpr *addressExpr ) {
845                AlternativeFinder finder( indexer, env );
846                finder.find( addressExpr->get_arg() );
847                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
848                        if ( isLvalue( i->expr ) ) {
849                                alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
850                        } // if
851                } // for
852        }
853
854        void AlternativeFinder::visit( LabelAddressExpr * expr ) {
855                alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) );
856        }
857
858        Expression * restructureCast( Expression * argExpr, Type * toType ) {
859                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
860                        // Argument expression is a tuple and the target type is not void and not a reference type.
861                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
862                        // cast expressions. If there are more components of the tuple than components in the target type,
863                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
864                        // side effects will still be done).
865                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
866                                // expressions which may contain side effects require a single unique instance of the expression.
867                                argExpr = new UniqueExpr( argExpr );
868                        }
869                        std::list< Expression * > componentExprs;
870                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
871                                // cast each component
872                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
873                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ) ) );
874                        }
875                        delete argExpr;
876                        assert( componentExprs.size() > 0 );
877                        // produce the tuple of casts
878                        return new TupleExpr( componentExprs );
879                } else {
880                        // handle normally
881                        return new CastExpr( argExpr, toType->clone() );
882                }
883        }
884
885        void AlternativeFinder::visit( CastExpr *castExpr ) {
886                Type *& toType = castExpr->get_result();
887                assert( toType );
888                toType = resolveTypeof( toType, indexer );
889                SymTab::validateType( toType, &indexer );
890                adjustExprType( toType, env, indexer );
891
892                AlternativeFinder finder( indexer, env );
893                finder.targetType = toType;
894                finder.findWithAdjustment( castExpr->get_arg() );
895
896                AltList candidates;
897                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
898                        AssertionSet needAssertions, haveAssertions;
899                        OpenVarSet openVars;
900
901                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
902                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
903                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
904                        // to.
905                        int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size();
906                        if ( discardedValues < 0 ) continue;
907                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
908                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
909                        // unification run for side-effects
910                        unify( castExpr->get_result(), i->expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
911                        Cost thisCost = castCost( i->expr->get_result(), castExpr->get_result(), indexer, i->env );
912                        if ( thisCost != Cost::infinity ) {
913                                // count one safe conversion for each value that is thrown away
914                                thisCost.incSafe( discardedValues );
915                                Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost );
916                                // xxx - this doesn't work at the moment, since inferParameters requires an ApplicationExpr as the alternative.
917                                // Once this works, it should be possible to infer parameters on a cast expression and specialize any function.
918
919                                // inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
920                                candidates.emplace_back( std::move( newAlt ) );
921                        } // if
922                } // for
923
924                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
925                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
926                // selects first based on argument cost, then on conversion cost.
927                AltList minArgCost;
928                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
929                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
930        }
931
932        void AlternativeFinder::visit( VirtualCastExpr * castExpr ) {
933                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
934                AlternativeFinder finder( indexer, env );
935                // don't prune here, since it's guaranteed all alternatives will have the same type
936                finder.findWithoutPrune( castExpr->get_arg() );
937                for ( Alternative & alt : finder.alternatives ) {
938                        alternatives.push_back( Alternative(
939                                new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
940                                alt.env, alt.cost ) );
941                }
942        }
943
944        void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
945                AlternativeFinder funcFinder( indexer, env );
946                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
947                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
948                        // 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
949                        std::unique_ptr<Expression> aggrExpr( agg->expr->clone() );
950                        Type * aggrType = aggrExpr->get_result();
951                        if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
952                                aggrType = aggrType->stripReferences();
953                                aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
954                        }
955                        // find member of the given type
956                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
957                                addAggMembers( structInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
958                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
959                                addAggMembers( unionInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
960                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
961                                addTupleMembers( tupleType, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
962                        } // if
963                } // for
964        }
965
966        void AlternativeFinder::visit( MemberExpr *memberExpr ) {
967                alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
968        }
969
970        void AlternativeFinder::visit( NameExpr *nameExpr ) {
971                std::list< DeclarationWithType* > declList;
972                indexer.lookupId( nameExpr->get_name(), declList );
973                PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
974                for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
975                        VariableExpr newExpr( *i );
976                        alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
977                        PRINT(
978                                std::cerr << "decl is ";
979                                (*i)->print( std::cerr );
980                                std::cerr << std::endl;
981                                std::cerr << "newExpr is ";
982                                newExpr.print( std::cerr );
983                                std::cerr << std::endl;
984                        )
985                        renameTypes( alternatives.back().expr );
986                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
987                } // for
988        }
989
990        void AlternativeFinder::visit( VariableExpr *variableExpr ) {
991                // not sufficient to clone here, because variable's type may have changed
992                // since the VariableExpr was originally created.
993                alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
994        }
995
996        void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
997                alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
998        }
999
1000        void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
1001                if ( sizeofExpr->get_isType() ) {
1002                        Type * newType = sizeofExpr->get_type()->clone();
1003                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1004                } else {
1005                        // find all alternatives for the argument to sizeof
1006                        AlternativeFinder finder( indexer, env );
1007                        finder.find( sizeofExpr->get_expr() );
1008                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1009                        AltList winners;
1010                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1011                        if ( winners.size() != 1 ) {
1012                                throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
1013                        } // if
1014                        // return the lowest cost alternative for the argument
1015                        Alternative &choice = winners.front();
1016                        referenceToRvalueConversion( choice.expr );
1017                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1018                } // if
1019        }
1020
1021        void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
1022                if ( alignofExpr->get_isType() ) {
1023                        Type * newType = alignofExpr->get_type()->clone();
1024                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1025                } else {
1026                        // find all alternatives for the argument to sizeof
1027                        AlternativeFinder finder( indexer, env );
1028                        finder.find( alignofExpr->get_expr() );
1029                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1030                        AltList winners;
1031                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1032                        if ( winners.size() != 1 ) {
1033                                throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
1034                        } // if
1035                        // return the lowest cost alternative for the argument
1036                        Alternative &choice = winners.front();
1037                        referenceToRvalueConversion( choice.expr );
1038                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1039                } // if
1040        }
1041
1042        template< typename StructOrUnionType >
1043        void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1044                std::list< Declaration* > members;
1045                aggInst->lookup( name, members );
1046                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1047                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1048                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1049                                renameTypes( alternatives.back().expr );
1050                        } else {
1051                                assert( false );
1052                        }
1053                }
1054        }
1055
1056        void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
1057                AlternativeFinder funcFinder( indexer, env );
1058                // xxx - resolveTypeof?
1059                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1060                        addOffsetof( structInst, offsetofExpr->get_member() );
1061                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1062                        addOffsetof( unionInst, offsetofExpr->get_member() );
1063                }
1064        }
1065
1066        void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
1067                alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
1068        }
1069
1070        void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
1071                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
1072        }
1073
1074        void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
1075                // assume no polymorphism
1076                // assume no implicit conversions
1077                assert( function->get_parameters().size() == 1 );
1078                PRINT(
1079                        std::cerr << "resolvAttr: funcDecl is ";
1080                        funcDecl->print( std::cerr );
1081                        std::cerr << " argType is ";
1082                        argType->print( std::cerr );
1083                        std::cerr << std::endl;
1084                )
1085                if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1086                        alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
1087                        for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
1088                                alternatives.back().expr->set_result( (*i)->get_type()->clone() );
1089                        } // for
1090                } // if
1091        }
1092
1093        void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1094                // assume no 'pointer-to-attribute'
1095                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1096                assert( nameExpr );
1097                std::list< DeclarationWithType* > attrList;
1098                indexer.lookupId( nameExpr->get_name(), attrList );
1099                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1100                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1101                                // check if the type is function
1102                                if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1103                                        // assume exactly one parameter
1104                                        if ( function->get_parameters().size() == 1 ) {
1105                                                if ( attrExpr->get_isType() ) {
1106                                                        resolveAttr( *i, function, attrExpr->get_type(), env );
1107                                                } else {
1108                                                        AlternativeFinder finder( indexer, env );
1109                                                        finder.find( attrExpr->get_expr() );
1110                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1111                                                                if ( choice->expr->get_result()->size() == 1 ) {
1112                                                                        resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1113                                                                } // fi
1114                                                        } // for
1115                                                } // if
1116                                        } // if
1117                                } // if
1118                        } // for
1119                } else {
1120                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1121                                VariableExpr newExpr( *i );
1122                                alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
1123                                renameTypes( alternatives.back().expr );
1124                        } // for
1125                } // if
1126        }
1127
1128        void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1129                AlternativeFinder firstFinder( indexer, env );
1130                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1131                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1132                        AlternativeFinder secondFinder( indexer, first->env );
1133                        secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1134                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1135                                LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1136                                alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1137                        }
1138                }
1139        }
1140
1141        void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1142                // find alternatives for condition
1143                AlternativeFinder firstFinder( indexer, env );
1144                firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1145                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1146                        // find alternatives for true expression
1147                        AlternativeFinder secondFinder( indexer, first->env );
1148                        secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1149                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1150                                // find alterantives for false expression
1151                                AlternativeFinder thirdFinder( indexer, second->env );
1152                                thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1153                                for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1154                                        // unify true and false types, then infer parameters to produce new alternatives
1155                                        OpenVarSet openVars;
1156                                        AssertionSet needAssertions, haveAssertions;
1157                                        Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1158                                        Type* commonType = nullptr;
1159                                        if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1160                                                ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1161                                                newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1162                                                // convert both options to the conditional result type
1163                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1164                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1165                                                newAlt.expr = newExpr;
1166                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1167                                        } // if
1168                                } // for
1169                        } // for
1170                } // for
1171        }
1172
1173        void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1174                TypeEnvironment newEnv( env );
1175                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1176                AlternativeFinder secondFinder( indexer, newEnv );
1177                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1178                for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1179                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1180                } // for
1181                delete newFirstArg;
1182        }
1183
1184        void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1185                // resolve low and high, accept alternatives whose low and high types unify
1186                AlternativeFinder firstFinder( indexer, env );
1187                firstFinder.findWithAdjustment( rangeExpr->get_low() );
1188                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1189                        AlternativeFinder secondFinder( indexer, first->env );
1190                        secondFinder.findWithAdjustment( rangeExpr->get_high() );
1191                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1192                                OpenVarSet openVars;
1193                                AssertionSet needAssertions, haveAssertions;
1194                                Alternative newAlt( 0, second->env, first->cost + second->cost );
1195                                Type* commonType = nullptr;
1196                                if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1197                                        RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1198                                        newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1199                                        newAlt.expr = newExpr;
1200                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1201                                } // if
1202                        } // for
1203                } // for
1204        }
1205
1206        void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1207                std::list< AlternativeFinder > subExprAlternatives;
1208                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1209                std::list< AltList > possibilities;
1210                combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1211                for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1212                        std::list< Expression * > exprs;
1213                        makeExprList( *i, exprs );
1214
1215                        TypeEnvironment compositeEnv;
1216                        simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1217                        alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
1218                } // for
1219        }
1220
1221        void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1222                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1223        }
1224
1225        void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1226                alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1227        }
1228
1229        void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1230                AlternativeFinder finder( indexer, env );
1231                // don't prune here, since it's guaranteed all alternatives will have the same type
1232                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1233                finder.findWithoutPrune( ctorExpr->get_callExpr() );
1234                for ( Alternative & alt : finder.alternatives ) {
1235                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1236                }
1237        }
1238
1239        void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1240                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1241        }
1242
1243        void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1244                alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1245        }
1246
1247        void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1248                AlternativeFinder finder( indexer, env );
1249                finder.findWithAdjustment( unqExpr->get_expr() );
1250                for ( Alternative & alt : finder.alternatives ) {
1251                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1252                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1253                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1254                }
1255        }
1256
1257        void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1258                StmtExpr * newStmtExpr = stmtExpr->clone();
1259                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1260                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1261                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1262        }
1263
1264        void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
1265                // handle each option like a cast
1266                AltList candidates;
1267                PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
1268                // O(N^2) checks of d-types with e-types
1269                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1270                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
1271                        SymTab::validateType( toType, &indexer );
1272                        adjustExprType( toType, env, indexer );
1273                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1274                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1275                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1276                        AlternativeFinder finder( indexer, env );
1277                        finder.targetType = toType;
1278                        finder.findWithAdjustment( initExpr->get_expr() );
1279                        for ( Alternative & alt : finder.get_alternatives() ) {
1280                                TypeEnvironment newEnv( alt.env );
1281                                AssertionSet needAssertions, haveAssertions;
1282                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
1283                                PRINT( std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl; )
1284                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1285                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1286                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1287                                // to.
1288                                int discardedValues = alt.expr->get_result()->size() - toType->size();
1289                                if ( discardedValues < 0 ) continue;
1290                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1291                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1292                                // unification run for side-effects
1293                                unify( toType, alt.expr->get_result(), newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type??
1294
1295                                Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
1296                                if ( thisCost != Cost::infinity ) {
1297                                        // count one safe conversion for each value that is thrown away
1298                                        thisCost.incSafe( discardedValues );
1299                                        candidates.push_back( Alternative( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost ) );
1300                                }
1301                        }
1302                }
1303
1304                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1305                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1306                // selects first based on argument cost, then on conversion cost.
1307                AltList minArgCost;
1308                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1309                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1310        }
1311} // namespace ResolvExpr
1312
1313// Local Variables: //
1314// tab-width: 4 //
1315// mode: c++ //
1316// compile-command: "make install" //
1317// End: //
Note: See TracBrowser for help on using the repository browser.