source: src/ResolvExpr/AlternativeFinder.cc @ bb666f64

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

Fix polymorphic-to-monomorphic function specialization for casts and initializers [fixes #27]

  • Property mode set to 100644
File size: 60.6 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
322                // if there is a non-zero conversion cost, ignoring poly cost, then the expression requires conversion.
323                // ignore poly cost for now, since this requires resolution of the cast to infer parameters and this
324                // does not currently work for the reason stated below.
325                Cost tmpCost = convCost;
326                tmpCost.incPoly( -tmpCost.get_polyCost() );
327                if ( tmpCost != Cost::zero ) {
328                // if ( convCost != 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                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
917                        } // if
918                } // for
919
920                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
921                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
922                // selects first based on argument cost, then on conversion cost.
923                AltList minArgCost;
924                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
925                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
926        }
927
928        void AlternativeFinder::visit( VirtualCastExpr * castExpr ) {
929                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
930                AlternativeFinder finder( indexer, env );
931                // don't prune here, since it's guaranteed all alternatives will have the same type
932                finder.findWithoutPrune( castExpr->get_arg() );
933                for ( Alternative & alt : finder.alternatives ) {
934                        alternatives.push_back( Alternative(
935                                new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
936                                alt.env, alt.cost ) );
937                }
938        }
939
940        void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
941                AlternativeFinder funcFinder( indexer, env );
942                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
943                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
944                        // 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
945                        std::unique_ptr<Expression> aggrExpr( agg->expr->clone() );
946                        Type * aggrType = aggrExpr->get_result();
947                        if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
948                                aggrType = aggrType->stripReferences();
949                                aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
950                        }
951                        // find member of the given type
952                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
953                                addAggMembers( structInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
954                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
955                                addAggMembers( unionInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
956                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
957                                addTupleMembers( tupleType, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
958                        } // if
959                } // for
960        }
961
962        void AlternativeFinder::visit( MemberExpr *memberExpr ) {
963                alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
964        }
965
966        void AlternativeFinder::visit( NameExpr *nameExpr ) {
967                std::list< DeclarationWithType* > declList;
968                indexer.lookupId( nameExpr->get_name(), declList );
969                PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
970                for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
971                        VariableExpr newExpr( *i );
972                        alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
973                        PRINT(
974                                std::cerr << "decl is ";
975                                (*i)->print( std::cerr );
976                                std::cerr << std::endl;
977                                std::cerr << "newExpr is ";
978                                newExpr.print( std::cerr );
979                                std::cerr << std::endl;
980                        )
981                        renameTypes( alternatives.back().expr );
982                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
983                } // for
984        }
985
986        void AlternativeFinder::visit( VariableExpr *variableExpr ) {
987                // not sufficient to clone here, because variable's type may have changed
988                // since the VariableExpr was originally created.
989                alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
990        }
991
992        void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
993                alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
994        }
995
996        void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
997                if ( sizeofExpr->get_isType() ) {
998                        Type * newType = sizeofExpr->get_type()->clone();
999                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1000                } else {
1001                        // find all alternatives for the argument to sizeof
1002                        AlternativeFinder finder( indexer, env );
1003                        finder.find( sizeofExpr->get_expr() );
1004                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1005                        AltList winners;
1006                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1007                        if ( winners.size() != 1 ) {
1008                                throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
1009                        } // if
1010                        // return the lowest cost alternative for the argument
1011                        Alternative &choice = winners.front();
1012                        referenceToRvalueConversion( choice.expr );
1013                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1014                } // if
1015        }
1016
1017        void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
1018                if ( alignofExpr->get_isType() ) {
1019                        Type * newType = alignofExpr->get_type()->clone();
1020                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1021                } else {
1022                        // find all alternatives for the argument to sizeof
1023                        AlternativeFinder finder( indexer, env );
1024                        finder.find( alignofExpr->get_expr() );
1025                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1026                        AltList winners;
1027                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1028                        if ( winners.size() != 1 ) {
1029                                throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
1030                        } // if
1031                        // return the lowest cost alternative for the argument
1032                        Alternative &choice = winners.front();
1033                        referenceToRvalueConversion( choice.expr );
1034                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1035                } // if
1036        }
1037
1038        template< typename StructOrUnionType >
1039        void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1040                std::list< Declaration* > members;
1041                aggInst->lookup( name, members );
1042                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1043                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1044                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1045                                renameTypes( alternatives.back().expr );
1046                        } else {
1047                                assert( false );
1048                        }
1049                }
1050        }
1051
1052        void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
1053                AlternativeFinder funcFinder( indexer, env );
1054                // xxx - resolveTypeof?
1055                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1056                        addOffsetof( structInst, offsetofExpr->get_member() );
1057                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1058                        addOffsetof( unionInst, offsetofExpr->get_member() );
1059                }
1060        }
1061
1062        void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
1063                alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
1064        }
1065
1066        void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
1067                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
1068        }
1069
1070        void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
1071                // assume no polymorphism
1072                // assume no implicit conversions
1073                assert( function->get_parameters().size() == 1 );
1074                PRINT(
1075                        std::cerr << "resolvAttr: funcDecl is ";
1076                        funcDecl->print( std::cerr );
1077                        std::cerr << " argType is ";
1078                        argType->print( std::cerr );
1079                        std::cerr << std::endl;
1080                )
1081                if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1082                        alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
1083                        for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
1084                                alternatives.back().expr->set_result( (*i)->get_type()->clone() );
1085                        } // for
1086                } // if
1087        }
1088
1089        void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1090                // assume no 'pointer-to-attribute'
1091                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1092                assert( nameExpr );
1093                std::list< DeclarationWithType* > attrList;
1094                indexer.lookupId( nameExpr->get_name(), attrList );
1095                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1096                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1097                                // check if the type is function
1098                                if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1099                                        // assume exactly one parameter
1100                                        if ( function->get_parameters().size() == 1 ) {
1101                                                if ( attrExpr->get_isType() ) {
1102                                                        resolveAttr( *i, function, attrExpr->get_type(), env );
1103                                                } else {
1104                                                        AlternativeFinder finder( indexer, env );
1105                                                        finder.find( attrExpr->get_expr() );
1106                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1107                                                                if ( choice->expr->get_result()->size() == 1 ) {
1108                                                                        resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1109                                                                } // fi
1110                                                        } // for
1111                                                } // if
1112                                        } // if
1113                                } // if
1114                        } // for
1115                } else {
1116                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1117                                VariableExpr newExpr( *i );
1118                                alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
1119                                renameTypes( alternatives.back().expr );
1120                        } // for
1121                } // if
1122        }
1123
1124        void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1125                AlternativeFinder firstFinder( indexer, env );
1126                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1127                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1128                        AlternativeFinder secondFinder( indexer, first->env );
1129                        secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1130                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1131                                LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1132                                alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1133                        }
1134                }
1135        }
1136
1137        void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1138                // find alternatives for condition
1139                AlternativeFinder firstFinder( indexer, env );
1140                firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1141                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1142                        // find alternatives for true expression
1143                        AlternativeFinder secondFinder( indexer, first->env );
1144                        secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1145                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1146                                // find alterantives for false expression
1147                                AlternativeFinder thirdFinder( indexer, second->env );
1148                                thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1149                                for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1150                                        // unify true and false types, then infer parameters to produce new alternatives
1151                                        OpenVarSet openVars;
1152                                        AssertionSet needAssertions, haveAssertions;
1153                                        Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1154                                        Type* commonType = nullptr;
1155                                        if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1156                                                ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1157                                                newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1158                                                // convert both options to the conditional result type
1159                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1160                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1161                                                newAlt.expr = newExpr;
1162                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1163                                        } // if
1164                                } // for
1165                        } // for
1166                } // for
1167        }
1168
1169        void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1170                TypeEnvironment newEnv( env );
1171                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1172                AlternativeFinder secondFinder( indexer, newEnv );
1173                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1174                for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1175                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1176                } // for
1177                delete newFirstArg;
1178        }
1179
1180        void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1181                // resolve low and high, accept alternatives whose low and high types unify
1182                AlternativeFinder firstFinder( indexer, env );
1183                firstFinder.findWithAdjustment( rangeExpr->get_low() );
1184                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1185                        AlternativeFinder secondFinder( indexer, first->env );
1186                        secondFinder.findWithAdjustment( rangeExpr->get_high() );
1187                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1188                                OpenVarSet openVars;
1189                                AssertionSet needAssertions, haveAssertions;
1190                                Alternative newAlt( 0, second->env, first->cost + second->cost );
1191                                Type* commonType = nullptr;
1192                                if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1193                                        RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1194                                        newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1195                                        newAlt.expr = newExpr;
1196                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1197                                } // if
1198                        } // for
1199                } // for
1200        }
1201
1202        void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1203                std::list< AlternativeFinder > subExprAlternatives;
1204                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1205                std::list< AltList > possibilities;
1206                combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1207                for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1208                        std::list< Expression * > exprs;
1209                        makeExprList( *i, exprs );
1210
1211                        TypeEnvironment compositeEnv;
1212                        simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1213                        alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
1214                } // for
1215        }
1216
1217        void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1218                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1219        }
1220
1221        void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1222                alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1223        }
1224
1225        void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1226                AlternativeFinder finder( indexer, env );
1227                // don't prune here, since it's guaranteed all alternatives will have the same type
1228                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1229                finder.findWithoutPrune( ctorExpr->get_callExpr() );
1230                for ( Alternative & alt : finder.alternatives ) {
1231                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1232                }
1233        }
1234
1235        void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1236                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1237        }
1238
1239        void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1240                alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1241        }
1242
1243        void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1244                AlternativeFinder finder( indexer, env );
1245                finder.findWithAdjustment( unqExpr->get_expr() );
1246                for ( Alternative & alt : finder.alternatives ) {
1247                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1248                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1249                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1250                }
1251        }
1252
1253        void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1254                StmtExpr * newStmtExpr = stmtExpr->clone();
1255                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1256                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1257                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1258        }
1259
1260        void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
1261                // handle each option like a cast
1262                AltList candidates;
1263                PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
1264                // O(N^2) checks of d-types with e-types
1265                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1266                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
1267                        SymTab::validateType( toType, &indexer );
1268                        adjustExprType( toType, env, indexer );
1269                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1270                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1271                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1272                        AlternativeFinder finder( indexer, env );
1273                        finder.targetType = toType;
1274                        finder.findWithAdjustment( initExpr->get_expr() );
1275                        for ( Alternative & alt : finder.get_alternatives() ) {
1276                                TypeEnvironment newEnv( alt.env );
1277                                AssertionSet needAssertions, haveAssertions;
1278                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
1279                                PRINT( std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl; )
1280                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1281                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1282                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1283                                // to.
1284                                int discardedValues = alt.expr->get_result()->size() - toType->size();
1285                                if ( discardedValues < 0 ) continue;
1286                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1287                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1288                                // unification run for side-effects
1289                                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??
1290
1291                                Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
1292                                if ( thisCost != Cost::infinity ) {
1293                                        // count one safe conversion for each value that is thrown away
1294                                        thisCost.incSafe( discardedValues );
1295                                        Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost );
1296                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
1297                                }
1298                        }
1299                }
1300
1301                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1302                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1303                // selects first based on argument cost, then on conversion cost.
1304                AltList minArgCost;
1305                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1306                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1307        }
1308} // namespace ResolvExpr
1309
1310// Local Variables: //
1311// tab-width: 4 //
1312// mode: c++ //
1313// compile-command: "make install" //
1314// End: //
Note: See TracBrowser for help on using the repository browser.