source: src/ResolvExpr/AlternativeFinder.cc @ 228099e

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 228099e was 228099e, checked in by Rob Schluntz <rschlunt@…>, 5 years ago

Fix ownership bug in initialization resolution

  • 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                                        }
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                for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
183                        if ( adjust ) {
184                                adjustExprType( i->expr->get_result(), i->env, indexer );
185                        }
186                }
187                if ( prune ) {
188                        PRINT(
189                                std::cerr << "alternatives before prune:" << std::endl;
190                                printAlts( alternatives, std::cerr );
191                        )
192                        AltList::iterator oldBegin = alternatives.begin();
193                        pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) );
194                        if ( failFast && alternatives.begin() == oldBegin ) {
195                                std::ostringstream stream;
196                                AltList winners;
197                                findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
198                                stream << "Cannot choose between " << winners.size() << " alternatives for expression\n";
199                                expr->print( stream );
200                                stream << "Alternatives are:\n";
201                                printAlts( winners, stream, 1 );
202                                throw SemanticError( stream.str() );
203                        }
204                        alternatives.erase( oldBegin, alternatives.end() );
205                        PRINT(
206                                std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
207                        )
208                }
209
210                // Central location to handle gcc extension keyword, etc. for all expression types.
211                for ( Alternative &iter: alternatives ) {
212                        iter.expr->set_extension( expr->get_extension() );
213                        iter.expr->location = expr->location;
214                } // for
215        }
216
217        void AlternativeFinder::findWithAdjustment( Expression *expr ) {
218                find( expr, true );
219        }
220
221        void AlternativeFinder::findWithoutPrune( Expression * expr ) {
222                find( expr, true, false );
223        }
224
225        void AlternativeFinder::maybeFind( Expression * expr ) {
226                find( expr, true, true, false );
227        }
228
229        void AlternativeFinder::addAnonConversions( const Alternative & alt ) {
230                // adds anonymous member interpretations whenever an aggregate value type is seen.
231                // 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
232                std::unique_ptr<Expression> aggrExpr( alt.expr->clone() );
233                alt.env.apply( aggrExpr->get_result() );
234                Type * aggrType = aggrExpr->get_result();
235                if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
236                        aggrType = aggrType->stripReferences();
237                        aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
238                }
239
240                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
241                        NameExpr nameExpr( "" );
242                        addAggMembers( structInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
243                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
244                        NameExpr nameExpr( "" );
245                        addAggMembers( unionInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
246                } // if
247        }
248
249        template< typename StructOrUnionType >
250        void AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
251                // by this point, member must be a name expr
252                NameExpr * nameExpr = dynamic_cast< NameExpr * >( member );
253                if ( ! nameExpr ) return;
254                const std::string & name = nameExpr->get_name();
255                std::list< Declaration* > members;
256                aggInst->lookup( name, members );
257
258                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
259                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
260                                alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
261                                renameTypes( alternatives.back().expr );
262                                addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
263                        } else {
264                                assert( false );
265                        }
266                }
267        }
268
269        void AlternativeFinder::addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
270                if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
271                        // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
272                        // xxx - this should be improved by memoizing the value of constant exprs
273                        // during parsing and reusing that information here.
274                        std::stringstream ss( constantExpr->get_constant()->get_value() );
275                        int val = 0;
276                        std::string tmp;
277                        if ( ss >> val && ! (ss >> tmp) ) {
278                                if ( val >= 0 && (unsigned int)val < tupleType->size() ) {
279                                        alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
280                                } // if
281                        } // if
282                } else if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( member ) ) {
283                        // xxx - temporary hack until 0/1 are int constants
284                        if ( nameExpr->get_name() == "0" || nameExpr->get_name() == "1" ) {
285                                std::stringstream ss( nameExpr->get_name() );
286                                int val;
287                                ss >> val;
288                                alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
289                        }
290                } // if
291        }
292
293        void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
294                alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
295        }
296
297        Cost computeConversionCost( Type * actualType, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
298                PRINT(
299                        std::cerr << std::endl << "converting ";
300                        actualType->print( std::cerr, 8 );
301                        std::cerr << std::endl << " to ";
302                        formalType->print( std::cerr, 8 );
303                        std::cerr << std::endl << "environment is: ";
304                        env.print( std::cerr, 8 );
305                        std::cerr << std::endl;
306                )
307                Cost convCost = conversionCost( actualType, formalType, indexer, env );
308                PRINT(
309                        std::cerr << std::endl << "cost is" << convCost << std::endl;
310                )
311                if ( convCost == Cost::infinity ) {
312                        return convCost;
313                }
314                convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) );
315                return convCost;
316        }
317
318        Cost computeExpressionConversionCost( Expression *& actualExpr, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
319                Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env );
320                // if ( convCost != Cost::zero ) {
321
322                // xxx - temporary -- ignore poly cost, since this causes some polymorphic functions to be cast, which causes the specialize
323                // pass to try to specialize them, which currently does not work. Once that is fixed, remove the next 3 lines and uncomment the
324                // previous line.
325                Cost tmpCost = convCost;
326                tmpCost.incPoly( -tmpCost.get_polyCost() );
327                if ( tmpCost != Cost::zero ) {
328                        Type *newType = formalType->clone();
329                        env.apply( newType );
330                        actualExpr = new CastExpr( actualExpr, newType );
331                        // 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
332                        // inconsistent, once this is fixed it should be possible to resolve the cast.
333                        // 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.
334
335                        // AlternativeFinder finder( indexer, env );
336                        // finder.findWithAdjustment( actualExpr );
337                        // assertf( finder.get_alternatives().size() > 0, "Somehow castable expression failed to find alternatives." );
338                        // assertf( finder.get_alternatives().size() == 1, "Somehow got multiple alternatives for known cast expression." );
339                        // Alternative & alt = finder.get_alternatives().front();
340                        // delete actualExpr;
341                        // actualExpr = alt.expr->clone();
342                }
343                return convCost;
344        }
345
346        Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
347                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( alt.expr );
348                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
349                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
350
351                Cost convCost = Cost::zero;
352                std::list< DeclarationWithType* >& formals = function->get_parameters();
353                std::list< DeclarationWithType* >::iterator formal = formals.begin();
354                std::list< Expression* >& actuals = appExpr->get_args();
355
356                for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
357                        Type * actualType = (*actualExpr)->get_result();
358                        PRINT(
359                                std::cerr << "actual expression:" << std::endl;
360                                (*actualExpr)->print( std::cerr, 8 );
361                                std::cerr << "--- results are" << std::endl;
362                                actualType->print( std::cerr, 8 );
363                        )
364                        if ( formal == formals.end() ) {
365                                if ( function->get_isVarArgs() ) {
366                                        convCost.incUnsafe();
367                                        // convert reference-typed expressions to value-typed expressions
368                                        referenceToRvalueConversion( *actualExpr );
369                                        continue;
370                                } else {
371                                        return Cost::infinity;
372                                }
373                        }
374                        Type * formalType = (*formal)->get_type();
375                        PRINT(
376                                std::cerr << std::endl << "converting ";
377                                actualType->print( std::cerr, 8 );
378                                std::cerr << std::endl << " to ";
379                                formalType->print( std::cerr, 8 );
380                                std::cerr << std::endl << "environment is: ";
381                                alt.env.print( std::cerr, 8 );
382                                std::cerr << std::endl;
383                        )
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                                assert( (*candidate)->get_uniqueId() );
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                                ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr );
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 = &appExpr->get_inferParams();
636                                for ( UniqueId id : cur->second.idChain ) {
637                                        inferParameters = (*inferParameters)[ id ].inferParams.get();
638                                }
639                                // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
640                                (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
641                                inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /*newNeedParents,*/ level, indexer, out );
642                        } else {
643                                delete adjType;
644                        }
645                }
646        }
647
648        template< typename OutputIterator >
649        void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
650//      PRINT(
651//          std::cerr << "inferParameters: assertions needed are" << std::endl;
652//          printAll( need, std::cerr, 8 );
653//          )
654                SymTab::Indexer decls( indexer );
655                // PRINT(
656                //      std::cerr << "============= original indexer" << std::endl;
657                //      indexer.print( std::cerr );
658                //      std::cerr << "============= new indexer" << std::endl;
659                //      decls.print( std::cerr );
660                // )
661                addToIndexer( have, decls );
662                AssertionSet newNeed;
663                //AssertionParentSet needParents;
664                PRINT(
665                        std::cerr << "env is: " << std::endl;
666                        newAlt.env.print( std::cerr, 0 );
667                        std::cerr << std::endl;
668                )
669
670                inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /*needParents,*/ 0, indexer, out );
671//      PRINT(
672//          std::cerr << "declaration 14 is ";
673//          Declaration::declFromId
674//          *out++ = newAlt;
675//          )
676        }
677
678        template< typename OutputIterator >
679        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) {
680                OpenVarSet openVars;
681                AssertionSet resultNeed, resultHave;
682                TypeEnvironment resultEnv;
683                makeUnifiableVars( funcType, openVars, resultNeed );
684                resultEnv.add( funcType->get_forall() ); // add all type variables as open variables now so that those not used in the parameter list are still considered open
685                AltList instantiatedActuals; // filled by instantiate function
686                if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
687                        // attempt to narrow based on expected target type
688                        Type * returnType = funcType->get_returnVals().front()->get_type();
689                        if ( ! unify( returnType, targetType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
690                                // unification failed, don't pursue this alternative
691                                return;
692                        }
693                }
694
695                if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) {
696                        ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
697                        Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) );
698                        makeExprList( instantiatedActuals, appExpr->get_args() );
699                        PRINT(
700                                std::cerr << "instantiate function success: " << appExpr << std::endl;
701                                std::cerr << "need assertions:" << std::endl;
702                                printAssertionSet( resultNeed, std::cerr, 8 );
703                        )
704                        inferParameters( resultNeed, resultHave, newAlt, openVars, out );
705                }
706        }
707
708        void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
709                AlternativeFinder funcFinder( indexer, env );
710                funcFinder.findWithAdjustment( untypedExpr->get_function() );
711                // if there are no function alternatives, then proceeding is a waste of time.
712                if ( funcFinder.alternatives.empty() ) return;
713
714                std::list< AlternativeFinder > argAlternatives;
715                findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );
716
717                std::list< AltList > possibilities;
718                combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
719
720                // take care of possible tuple assignments
721                // if not tuple assignment, assignment is taken care of as a normal function call
722                Tuples::handleTupleAssignment( *this, untypedExpr, possibilities );
723
724                // find function operators
725                static NameExpr *opExpr = new NameExpr( "?()" );
726                AlternativeFinder funcOpFinder( indexer, env );
727                // it's ok if there aren't any defined function ops
728                funcOpFinder.maybeFind( opExpr);
729                PRINT(
730                        std::cerr << "known function ops:" << std::endl;
731                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
732                )
733
734                AltList candidates;
735                SemanticError errors;
736                for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
737                        try {
738                                PRINT(
739                                        std::cerr << "working on alternative: " << std::endl;
740                                        func->print( std::cerr, 8 );
741                                )
742                                // check if the type is pointer to function
743                                if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->get_result()->stripReferences() ) ) {
744                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
745                                                Alternative newFunc( *func );
746                                                referenceToRvalueConversion( newFunc.expr );
747                                                for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
748                                                        // XXX
749                                                        //Designators::check_alternative( function, *actualAlt );
750                                                        makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) );
751                                                }
752                                        }
753                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
754                                        EqvClass eqvClass;
755                                        if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
756                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
757                                                        Alternative newFunc( *func );
758                                                        referenceToRvalueConversion( newFunc.expr );
759                                                        for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
760                                                                makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) );
761                                                        } // for
762                                                } // if
763                                        } // if
764                                }
765
766                                // try each function operator ?() with the current function alternative and each of the argument combinations
767                                for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
768                                        // check if the type is pointer to function
769                                        if ( PointerType *pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result()->stripReferences() ) ) {
770                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
771                                                        Alternative newFunc( *funcOp );
772                                                        referenceToRvalueConversion( newFunc.expr );
773                                                        for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
774                                                                AltList currentAlt;
775                                                                currentAlt.push_back( *func );
776                                                                currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
777                                                                makeFunctionAlternatives( newFunc, function, currentAlt, std::back_inserter( candidates ) );
778                                                        } // for
779                                                } // if
780                                        } // if
781                                } // for
782                        } catch ( SemanticError &e ) {
783                                errors.append( e );
784                        }
785                } // for
786
787                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
788                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
789
790                // compute conversionsion costs
791                for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
792                        Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer );
793
794                        PRINT(
795                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc->expr );
796                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
797                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
798                                std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
799                                std::cerr << "formals are:" << std::endl;
800                                printAll( function->get_parameters(), std::cerr, 8 );
801                                std::cerr << "actuals are:" << std::endl;
802                                printAll( appExpr->get_args(), std::cerr, 8 );
803                                std::cerr << "bindings are:" << std::endl;
804                                withFunc->env.print( std::cerr, 8 );
805                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
806                        )
807                        if ( cvtCost != Cost::infinity ) {
808                                withFunc->cvtCost = cvtCost;
809                                alternatives.push_back( *withFunc );
810                        } // if
811                } // for
812
813                candidates.clear();
814                candidates.splice( candidates.end(), alternatives );
815
816                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
817
818                // function may return struct or union value, in which case we need to add alternatives for implicit
819                // conversions to each of the anonymous members, must happen after findMinCost since anon conversions
820                // are never the cheapest expression
821                for ( const Alternative & alt : alternatives ) {
822                        addAnonConversions( alt );
823                }
824
825                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
826                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
827                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
828                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
829                        //   const char * x = "hello world";
830                        //   unsigned char ch = x[0];
831                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
832                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
833                        // fix this issue in a more robust way.
834                        targetType = nullptr;
835                        visit( untypedExpr );
836                }
837        }
838
839        bool isLvalue( Expression *expr ) {
840                // xxx - recurse into tuples?
841                return expr->result && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
842        }
843
844        void AlternativeFinder::visit( AddressExpr *addressExpr ) {
845                AlternativeFinder finder( indexer, env );
846                finder.find( addressExpr->get_arg() );
847                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
848                        if ( isLvalue( i->expr ) ) {
849                                alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
850                        } // if
851                } // for
852        }
853
854        void AlternativeFinder::visit( LabelAddressExpr * expr ) {
855                alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) );
856        }
857
858        Expression * restructureCast( Expression * argExpr, Type * toType ) {
859                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
860                        // Argument expression is a tuple and the target type is not void and not a reference type.
861                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
862                        // cast expressions. If there are more components of the tuple than components in the target type,
863                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
864                        // side effects will still be done).
865                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
866                                // expressions which may contain side effects require a single unique instance of the expression.
867                                argExpr = new UniqueExpr( argExpr );
868                        }
869                        std::list< Expression * > componentExprs;
870                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
871                                // cast each component
872                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
873                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ) ) );
874                        }
875                        delete argExpr;
876                        assert( componentExprs.size() > 0 );
877                        // produce the tuple of casts
878                        return new TupleExpr( componentExprs );
879                } else {
880                        // handle normally
881                        return new CastExpr( argExpr, toType->clone() );
882                }
883        }
884
885        void AlternativeFinder::visit( CastExpr *castExpr ) {
886                Type *& toType = castExpr->get_result();
887                assert( toType );
888                toType = resolveTypeof( toType, indexer );
889                SymTab::validateType( toType, &indexer );
890                adjustExprType( toType, env, indexer );
891
892                AlternativeFinder finder( indexer, env );
893                finder.targetType = toType;
894                finder.findWithAdjustment( castExpr->get_arg() );
895
896                AltList candidates;
897                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
898                        AssertionSet needAssertions, haveAssertions;
899                        OpenVarSet openVars;
900
901                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
902                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
903                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
904                        // to.
905                        int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size();
906                        if ( discardedValues < 0 ) continue;
907                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
908                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
909                        // unification run for side-effects
910                        unify( castExpr->get_result(), i->expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
911                        Cost thisCost = castCost( i->expr->get_result(), castExpr->get_result(), indexer, i->env );
912                        if ( thisCost != Cost::infinity ) {
913                                // count one safe conversion for each value that is thrown away
914                                thisCost.incSafe( discardedValues );
915                                Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost );
916                                // xxx - this doesn't work at the moment, since inferParameters requires an ApplicationExpr as the alternative.
917                                // Once this works, it should be possible to infer parameters on a cast expression and specialize any function.
918
919                                // inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
920                                candidates.emplace_back( std::move( newAlt ) );
921                        } // if
922                } // for
923
924                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
925                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
926                // selects first based on argument cost, then on conversion cost.
927                AltList minArgCost;
928                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
929                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
930        }
931
932        void AlternativeFinder::visit( VirtualCastExpr * castExpr ) {
933                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
934                AlternativeFinder finder( indexer, env );
935                // don't prune here, since it's guaranteed all alternatives will have the same type
936                finder.findWithoutPrune( castExpr->get_arg() );
937                for ( Alternative & alt : finder.alternatives ) {
938                        alternatives.push_back( Alternative(
939                                new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
940                                alt.env, alt.cost ) );
941                }
942        }
943
944        void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
945                AlternativeFinder funcFinder( indexer, env );
946                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
947                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
948                        // it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value
949                        std::unique_ptr<Expression> aggrExpr( agg->expr->clone() );
950                        Type * aggrType = aggrExpr->get_result();
951                        if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
952                                aggrType = aggrType->stripReferences();
953                                aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
954                        }
955                        // find member of the given type
956                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
957                                addAggMembers( structInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
958                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
959                                addAggMembers( unionInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
960                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
961                                addTupleMembers( tupleType, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
962                        } // if
963                } // for
964        }
965
966        void AlternativeFinder::visit( MemberExpr *memberExpr ) {
967                alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
968        }
969
970        void AlternativeFinder::visit( NameExpr *nameExpr ) {
971                std::list< DeclarationWithType* > declList;
972                indexer.lookupId( nameExpr->get_name(), declList );
973                PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
974                for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
975                        VariableExpr newExpr( *i );
976                        alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
977                        PRINT(
978                                std::cerr << "decl is ";
979                                (*i)->print( std::cerr );
980                                std::cerr << std::endl;
981                                std::cerr << "newExpr is ";
982                                newExpr.print( std::cerr );
983                                std::cerr << std::endl;
984                        )
985                        renameTypes( alternatives.back().expr );
986                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
987                } // for
988        }
989
990        void AlternativeFinder::visit( VariableExpr *variableExpr ) {
991                // not sufficient to clone here, because variable's type may have changed
992                // since the VariableExpr was originally created.
993                alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
994        }
995
996        void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
997                alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
998        }
999
1000        void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
1001                if ( sizeofExpr->get_isType() ) {
1002                        Type * newType = sizeofExpr->get_type()->clone();
1003                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1004                } else {
1005                        // find all alternatives for the argument to sizeof
1006                        AlternativeFinder finder( indexer, env );
1007                        finder.find( sizeofExpr->get_expr() );
1008                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1009                        AltList winners;
1010                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1011                        if ( winners.size() != 1 ) {
1012                                throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
1013                        } // if
1014                        // return the lowest cost alternative for the argument
1015                        Alternative &choice = winners.front();
1016                        referenceToRvalueConversion( choice.expr );
1017                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1018                } // if
1019        }
1020
1021        void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
1022                if ( alignofExpr->get_isType() ) {
1023                        Type * newType = alignofExpr->get_type()->clone();
1024                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1025                } else {
1026                        // find all alternatives for the argument to sizeof
1027                        AlternativeFinder finder( indexer, env );
1028                        finder.find( alignofExpr->get_expr() );
1029                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1030                        AltList winners;
1031                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1032                        if ( winners.size() != 1 ) {
1033                                throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
1034                        } // if
1035                        // return the lowest cost alternative for the argument
1036                        Alternative &choice = winners.front();
1037                        referenceToRvalueConversion( choice.expr );
1038                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1039                } // if
1040        }
1041
1042        template< typename StructOrUnionType >
1043        void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1044                std::list< Declaration* > members;
1045                aggInst->lookup( name, members );
1046                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1047                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1048                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1049                                renameTypes( alternatives.back().expr );
1050                        } else {
1051                                assert( false );
1052                        }
1053                }
1054        }
1055
1056        void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
1057                AlternativeFinder funcFinder( indexer, env );
1058                // xxx - resolveTypeof?
1059                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1060                        addOffsetof( structInst, offsetofExpr->get_member() );
1061                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1062                        addOffsetof( unionInst, offsetofExpr->get_member() );
1063                }
1064        }
1065
1066        void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
1067                alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
1068        }
1069
1070        void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
1071                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
1072        }
1073
1074        void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
1075                // assume no polymorphism
1076                // assume no implicit conversions
1077                assert( function->get_parameters().size() == 1 );
1078                PRINT(
1079                        std::cerr << "resolvAttr: funcDecl is ";
1080                        funcDecl->print( std::cerr );
1081                        std::cerr << " argType is ";
1082                        argType->print( std::cerr );
1083                        std::cerr << std::endl;
1084                )
1085                if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1086                        alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
1087                        for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
1088                                alternatives.back().expr->set_result( (*i)->get_type()->clone() );
1089                        } // for
1090                } // if
1091        }
1092
1093        void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1094                // assume no 'pointer-to-attribute'
1095                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1096                assert( nameExpr );
1097                std::list< DeclarationWithType* > attrList;
1098                indexer.lookupId( nameExpr->get_name(), attrList );
1099                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1100                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1101                                // check if the type is function
1102                                if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1103                                        // assume exactly one parameter
1104                                        if ( function->get_parameters().size() == 1 ) {
1105                                                if ( attrExpr->get_isType() ) {
1106                                                        resolveAttr( *i, function, attrExpr->get_type(), env );
1107                                                } else {
1108                                                        AlternativeFinder finder( indexer, env );
1109                                                        finder.find( attrExpr->get_expr() );
1110                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1111                                                                if ( choice->expr->get_result()->size() == 1 ) {
1112                                                                        resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1113                                                                } // fi
1114                                                        } // for
1115                                                } // if
1116                                        } // if
1117                                } // if
1118                        } // for
1119                } else {
1120                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1121                                VariableExpr newExpr( *i );
1122                                alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
1123                                renameTypes( alternatives.back().expr );
1124                        } // for
1125                } // if
1126        }
1127
1128        void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1129                AlternativeFinder firstFinder( indexer, env );
1130                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1131                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1132                        AlternativeFinder secondFinder( indexer, first->env );
1133                        secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1134                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1135                                LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1136                                alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1137                        }
1138                }
1139        }
1140
1141        void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1142                // find alternatives for condition
1143                AlternativeFinder firstFinder( indexer, env );
1144                firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1145                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1146                        // find alternatives for true expression
1147                        AlternativeFinder secondFinder( indexer, first->env );
1148                        secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1149                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1150                                // find alterantives for false expression
1151                                AlternativeFinder thirdFinder( indexer, second->env );
1152                                thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1153                                for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1154                                        // unify true and false types, then infer parameters to produce new alternatives
1155                                        OpenVarSet openVars;
1156                                        AssertionSet needAssertions, haveAssertions;
1157                                        Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1158                                        Type* commonType = nullptr;
1159                                        if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1160                                                ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1161                                                newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1162                                                // convert both options to the conditional result type
1163                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1164                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1165                                                newAlt.expr = newExpr;
1166                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1167                                        } // if
1168                                } // for
1169                        } // for
1170                } // for
1171        }
1172
1173        void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1174                TypeEnvironment newEnv( env );
1175                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1176                AlternativeFinder secondFinder( indexer, newEnv );
1177                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1178                for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1179                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1180                } // for
1181                delete newFirstArg;
1182        }
1183
1184        void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1185                // resolve low and high, accept alternatives whose low and high types unify
1186                AlternativeFinder firstFinder( indexer, env );
1187                firstFinder.findWithAdjustment( rangeExpr->get_low() );
1188                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1189                        AlternativeFinder secondFinder( indexer, first->env );
1190                        secondFinder.findWithAdjustment( rangeExpr->get_high() );
1191                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1192                                OpenVarSet openVars;
1193                                AssertionSet needAssertions, haveAssertions;
1194                                Alternative newAlt( 0, second->env, first->cost + second->cost );
1195                                Type* commonType = nullptr;
1196                                if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1197                                        RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1198                                        newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1199                                        newAlt.expr = newExpr;
1200                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1201                                } // if
1202                        } // for
1203                } // for
1204        }
1205
1206        void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1207                std::list< AlternativeFinder > subExprAlternatives;
1208                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1209                std::list< AltList > possibilities;
1210                combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1211                for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1212                        std::list< Expression * > exprs;
1213                        makeExprList( *i, exprs );
1214
1215                        TypeEnvironment compositeEnv;
1216                        simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1217                        alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
1218                } // for
1219        }
1220
1221        void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1222                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1223        }
1224
1225        void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1226                alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1227        }
1228
1229        void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1230                AlternativeFinder finder( indexer, env );
1231                // don't prune here, since it's guaranteed all alternatives will have the same type
1232                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1233                finder.findWithoutPrune( ctorExpr->get_callExpr() );
1234                for ( Alternative & alt : finder.alternatives ) {
1235                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1236                }
1237        }
1238
1239        void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1240                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1241        }
1242
1243        void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1244                alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1245        }
1246
1247        void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1248                AlternativeFinder finder( indexer, env );
1249                finder.findWithAdjustment( unqExpr->get_expr() );
1250                for ( Alternative & alt : finder.alternatives ) {
1251                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1252                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1253                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1254                }
1255        }
1256
1257        void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1258                StmtExpr * newStmtExpr = stmtExpr->clone();
1259                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1260                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1261                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1262        }
1263
1264        void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
1265                // handle each option like a cast
1266                AltList candidates;
1267                PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
1268                // O(N^2) checks of d-types with e-types
1269                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1270                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
1271                        SymTab::validateType( toType, &indexer );
1272                        adjustExprType( toType, env, indexer );
1273                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1274                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1275                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1276                        AlternativeFinder finder( indexer, env );
1277                        finder.targetType = toType;
1278                        finder.findWithAdjustment( initExpr->get_expr() );
1279                        for ( Alternative & alt : finder.get_alternatives() ) {
1280                                TypeEnvironment newEnv( alt.env );
1281                                AssertionSet needAssertions, haveAssertions;
1282                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
1283                                PRINT( std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl; )
1284                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1285                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1286                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1287                                // to.
1288                                int discardedValues = alt.expr->get_result()->size() - toType->size();
1289                                if ( discardedValues < 0 ) continue;
1290                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1291                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1292                                // unification run for side-effects
1293                                unify( toType, alt.expr->get_result(), newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type??
1294
1295                                Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
1296                                if ( thisCost != Cost::infinity ) {
1297                                        // count one safe conversion for each value that is thrown away
1298                                        thisCost.incSafe( discardedValues );
1299                                        candidates.push_back( Alternative( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost ) );
1300                                }
1301                        }
1302                }
1303
1304                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1305                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1306                // selects first based on argument cost, then on conversion cost.
1307                AltList minArgCost;
1308                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1309                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1310        }
1311} // namespace ResolvExpr
1312
1313// Local Variables: //
1314// tab-width: 4 //
1315// mode: c++ //
1316// compile-command: "make install" //
1317// End: //
Note: See TracBrowser for help on using the repository browser.