source: src/ResolvExpr/AlternativeFinder.cc @ d06c808

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

Update debug print in AlternativeFinder?

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