source: src/ResolvExpr/AlternativeFinder.cc @ c3b3799

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

Add maybeFind to AlternativeFinder? to prevent excess exceptions when finding function operators

  • 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, int indent = 0 ) {
78                        for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
79                                i->print( os, indent );
80                                os << std::endl;
81                        }
82                }
83
84                void makeExprList( const AltList &in, std::list< Expression* > &out ) {
85                        for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
86                                out.push_back( i->expr->clone() );
87                        }
88                }
89
90                struct PruneStruct {
91                        bool isAmbiguous;
92                        AltList::iterator candidate;
93                        PruneStruct() {}
94                        PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
95                };
96
97                /// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
98                template< typename InputIterator, typename OutputIterator >
99                void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out ) {
100                        // select the alternatives that have the minimum conversion cost for a particular set of result types
101                        std::map< std::string, PruneStruct > selected;
102                        for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
103                                PruneStruct current( candidate );
104                                std::string mangleName;
105                                {
106                                        Type * newType = candidate->expr->get_result()->clone();
107                                        candidate->env.apply( newType );
108                                        mangleName = SymTab::Mangler::mangle( newType );
109                                        delete newType;
110                                }
111                                std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
112                                if ( mapPlace != selected.end() ) {
113                                        if ( candidate->cost < mapPlace->second.candidate->cost ) {
114                                                PRINT(
115                                                        std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
116                                                )
117                                                selected[ mangleName ] = current;
118                                        } else if ( candidate->cost == mapPlace->second.candidate->cost ) {
119                                                PRINT(
120                                                        std::cerr << "marking ambiguous" << std::endl;
121                                                )
122                                                mapPlace->second.isAmbiguous = true;
123                                        }
124                                } else {
125                                        selected[ mangleName ] = current;
126                                }
127                        }
128
129                        PRINT(
130                                std::cerr << "there are " << selected.size() << " alternatives before elimination" << std::endl;
131                        )
132
133                        // accept the alternatives that were unambiguous
134                        for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
135                                if ( ! target->second.isAmbiguous ) {
136                                        Alternative &alt = *target->second.candidate;
137                                        alt.env.applyFree( alt.expr->get_result() );
138                                        *out++ = alt;
139                                }
140                        }
141                }
142
143                void renameTypes( Expression *expr ) {
144                        expr->get_result()->accept( global_renamer );
145                }
146        } // namespace
147
148        void referenceToRvalueConversion( Expression *& expr ) {
149                if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
150                        // cast away reference from expr
151                        expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() );
152                }
153        }
154
155        template< typename InputIterator, typename OutputIterator >
156        void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
157                while ( begin != end ) {
158                        AlternativeFinder finder( indexer, env );
159                        finder.findWithAdjustment( *begin );
160                        // XXX  either this
161                        //Designators::fixDesignations( finder, (*begin++)->get_argName() );
162                        // or XXX this
163                        begin++;
164                        PRINT(
165                                std::cerr << "findSubExprs" << std::endl;
166                                printAlts( finder.alternatives, std::cerr );
167                        )
168                        *out++ = finder;
169                }
170        }
171
172        AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
173                : indexer( indexer ), env( env ) {
174        }
175
176        void AlternativeFinder::find( Expression *expr, bool adjust, bool prune, bool failFast ) {
177                expr->accept( *this );
178                if ( failFast && alternatives.empty() ) {
179                        throw SemanticError( "No reasonable alternatives for expression ", expr );
180                }
181                for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
182                        if ( adjust ) {
183                                adjustExprType( i->expr->get_result(), i->env, indexer );
184                        }
185                }
186                if ( prune ) {
187                        PRINT(
188                                std::cerr << "alternatives before prune:" << std::endl;
189                                printAlts( alternatives, std::cerr );
190                        )
191                        AltList::iterator oldBegin = alternatives.begin();
192                        pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) );
193                        if ( failFast && alternatives.begin() == oldBegin ) {
194                                std::ostringstream stream;
195                                AltList winners;
196                                findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
197                                stream << "Cannot choose between " << winners.size() << " alternatives for expression ";
198                                expr->print( stream );
199                                stream << "Alternatives are:";
200                                printAlts( winners, stream, 8 );
201                                throw SemanticError( stream.str() );
202                        }
203                        alternatives.erase( oldBegin, alternatives.end() );
204                        PRINT(
205                                std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
206                        )
207                }
208
209                // Central location to handle gcc extension keyword, etc. for all expression types.
210                for ( Alternative &iter: alternatives ) {
211                        iter.expr->set_extension( expr->get_extension() );
212                        iter.expr->location = expr->location;
213                } // for
214        }
215
216        void AlternativeFinder::findWithAdjustment( Expression *expr ) {
217                find( expr, true );
218        }
219
220        void AlternativeFinder::findWithoutPrune( Expression * expr ) {
221                find( expr, true, false );
222        }
223
224        void AlternativeFinder::maybeFind( Expression * expr ) {
225                find( expr, true, true, false );
226        }
227
228        void AlternativeFinder::addAnonConversions( const Alternative & alt ) {
229                // adds anonymous member interpretations whenever an aggregate value type is seen.
230                // 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
231                std::unique_ptr<Expression> aggrExpr( alt.expr->clone() );
232                alt.env.apply( aggrExpr->get_result() );
233                Type * aggrType = aggrExpr->get_result();
234                if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
235                        aggrType = aggrType->stripReferences();
236                        aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
237                }
238
239                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
240                        NameExpr nameExpr( "" );
241                        addAggMembers( structInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
242                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
243                        NameExpr nameExpr( "" );
244                        addAggMembers( unionInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
245                } // if
246        }
247
248        template< typename StructOrUnionType >
249        void AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
250                // by this point, member must be a name expr
251                NameExpr * nameExpr = dynamic_cast< NameExpr * >( member );
252                if ( ! nameExpr ) return;
253                const std::string & name = nameExpr->get_name();
254                std::list< Declaration* > members;
255                aggInst->lookup( name, members );
256
257                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
258                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
259                                alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
260                                renameTypes( alternatives.back().expr );
261                                addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
262                        } else {
263                                assert( false );
264                        }
265                }
266        }
267
268        void AlternativeFinder::addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
269                if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
270                        // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
271                        // xxx - this should be improved by memoizing the value of constant exprs
272                        // during parsing and reusing that information here.
273                        std::stringstream ss( constantExpr->get_constant()->get_value() );
274                        int val = 0;
275                        std::string tmp;
276                        if ( ss >> val && ! (ss >> tmp) ) {
277                                if ( val >= 0 && (unsigned int)val < tupleType->size() ) {
278                                        alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
279                                } // if
280                        } // if
281                } else if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( member ) ) {
282                        // xxx - temporary hack until 0/1 are int constants
283                        if ( nameExpr->get_name() == "0" || nameExpr->get_name() == "1" ) {
284                                std::stringstream ss( nameExpr->get_name() );
285                                int val;
286                                ss >> val;
287                                alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
288                        }
289                } // if
290        }
291
292        void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
293                alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
294        }
295
296        Cost computeConversionCost( Type * actualType, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
297                PRINT(
298                        std::cerr << std::endl << "converting ";
299                        actualType->print( std::cerr, 8 );
300                        std::cerr << std::endl << " to ";
301                        formalType->print( std::cerr, 8 );
302                        std::cerr << std::endl << "environment is: ";
303                        env.print( std::cerr, 8 );
304                        std::cerr << std::endl;
305                )
306                Cost convCost = conversionCost( actualType, formalType, indexer, env );
307                PRINT(
308                        std::cerr << std::endl << "cost is" << convCost << std::endl;
309                )
310                if ( convCost == Cost::infinity ) {
311                        return convCost;
312                }
313                convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) );
314                return convCost;
315        }
316
317        Cost computeExpressionConversionCost( Expression *& actualExpr, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
318                Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env );
319                // if ( convCost != Cost::zero ) {
320
321                // xxx - temporary -- ignore poly cost, since this causes some polymorphic functions to be cast, which causes the specialize
322                // pass to try to specialize them, which currently does not work. Once that is fixed, remove the next 3 lines and uncomment the
323                // previous line.
324                Cost tmpCost = convCost;
325                tmpCost.incPoly( -tmpCost.get_polyCost() );
326                if ( tmpCost != Cost::zero ) {
327                        Type *newType = formalType->clone();
328                        env.apply( newType );
329                        actualExpr = new CastExpr( actualExpr, newType );
330                        // 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
331                        // inconsistent, once this is fixed it should be possible to resolve the cast.
332                        // 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.
333
334                        // AlternativeFinder finder( indexer, env );
335                        // finder.findWithAdjustment( actualExpr );
336                        // assertf( finder.get_alternatives().size() > 0, "Somehow castable expression failed to find alternatives." );
337                        // assertf( finder.get_alternatives().size() == 1, "Somehow got multiple alternatives for known cast expression." );
338                        // Alternative & alt = finder.get_alternatives().front();
339                        // delete actualExpr;
340                        // actualExpr = alt.expr->clone();
341                }
342                return convCost;
343        }
344
345        Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
346                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( alt.expr );
347                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
348                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
349
350                Cost convCost = Cost::zero;
351                std::list< DeclarationWithType* >& formals = function->get_parameters();
352                std::list< DeclarationWithType* >::iterator formal = formals.begin();
353                std::list< Expression* >& actuals = appExpr->get_args();
354
355                for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
356                        Type * actualType = (*actualExpr)->get_result();
357                        PRINT(
358                                std::cerr << "actual expression:" << std::endl;
359                                (*actualExpr)->print( std::cerr, 8 );
360                                std::cerr << "--- results are" << std::endl;
361                                actualType->print( std::cerr, 8 );
362                        )
363                        if ( formal == formals.end() ) {
364                                if ( function->get_isVarArgs() ) {
365                                        convCost.incUnsafe();
366                                        // convert reference-typed expressions to value-typed expressions
367                                        referenceToRvalueConversion( *actualExpr );
368                                        continue;
369                                } else {
370                                        return Cost::infinity;
371                                }
372                        }
373                        Type * formalType = (*formal)->get_type();
374                        PRINT(
375                                std::cerr << std::endl << "converting ";
376                                actualType->print( std::cerr, 8 );
377                                std::cerr << std::endl << " to ";
378                                formalType->print( std::cerr, 8 );
379                                std::cerr << std::endl << "environment is: ";
380                                alt.env.print( std::cerr, 8 );
381                                std::cerr << std::endl;
382                        )
383                        convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
384                        ++formal; // can't be in for-loop update because of the continue
385                }
386                if ( formal != formals.end() ) {
387                        return Cost::infinity;
388                }
389
390                for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
391                        convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
392                }
393
394                return convCost;
395        }
396
397        /// Adds type variables to the open variable set and marks their assertions
398        void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
399                for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
400                        unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar };
401                        for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
402                                needAssertions[ *assert ].isUsed = true;
403                        }
404///     needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
405                }
406        }
407
408        /// instantiate a single argument by matching actuals from [actualIt, actualEnd) against formalType,
409        /// producing expression(s) in out and their total cost in cost.
410        template< typename AltIterator, typename OutputIterator >
411        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 ) {
412                if ( TupleType * tupleType = dynamic_cast< TupleType * >( formalType ) ) {
413                        // formalType is a TupleType - group actuals into a TupleExpr whose type unifies with the TupleType
414                        std::list< Expression * > exprs;
415                        for ( Type * type : *tupleType ) {
416                                if ( ! instantiateArgument( type, defaultValue, actualIt, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( exprs ) ) ) {
417                                        deleteAll( exprs );
418                                        return false;
419                                }
420                        }
421                        *out++ = new TupleExpr( exprs );
422                } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
423                        // xxx - mixing default arguments with variadic??
424                        std::list< Expression * > exprs;
425                        for ( ; actualIt != actualEnd; ++actualIt ) {
426                                exprs.push_back( actualIt->expr->clone() );
427                                cost += actualIt->cost;
428                        }
429                        Expression * arg = nullptr;
430                        if ( exprs.size() == 1 && Tuples::isTtype( exprs.front()->get_result() ) ) {
431                                // the case where a ttype value is passed directly is special, e.g. for argument forwarding purposes
432                                // xxx - what if passing multiple arguments, last of which is ttype?
433                                // xxx - what would happen if unify was changed so that unifying tuple types flattened both before unifying lists? then pass in TupleType(ttype) below.
434                                arg = exprs.front();
435                        } else {
436                                arg = new TupleExpr( exprs );
437                        }
438                        assert( arg && arg->get_result() );
439                        if ( ! unify( ttype, arg->get_result(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
440                                return false;
441                        }
442                        *out++ = arg;
443                } else if ( actualIt != actualEnd ) {
444                        // both actualType and formalType are atomic (non-tuple) types - if they unify
445                        // then accept actual as an argument, otherwise return false (fail to instantiate argument)
446                        Expression * actual = actualIt->expr;
447                        Type * actualType = actual->get_result();
448
449                        PRINT(
450                                std::cerr << "formal type is ";
451                                formalType->print( std::cerr );
452                                std::cerr << std::endl << "actual type is ";
453                                actualType->print( std::cerr );
454                                std::cerr << std::endl;
455                        )
456                        if ( ! unify( formalType, actualType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
457                                // std::cerr << "unify failed" << std::endl;
458                                return false;
459                        }
460                        // move the expression from the alternative to the output iterator
461                        *out++ = actual;
462                        actualIt->expr = nullptr;
463                        cost += actualIt->cost;
464                        ++actualIt;
465                } else {
466                        // End of actuals - Handle default values
467                        if ( SingleInit *si = dynamic_cast<SingleInit *>( defaultValue )) {
468                                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( si->get_value() ) ) {
469                                        // so far, only constant expressions are accepted as default values
470                                        if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( castExpr->get_arg() ) ) {
471                                                if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) ) {
472                                                        if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
473                                                                *out++ = cnstexpr->clone();
474                                                                return true;
475                                                        } // if
476                                                } // if
477                                        } // if
478                                }
479                        } // if
480                        return false;
481                } // if
482                return true;
483        }
484
485        bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) {
486                simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
487                // make sure we don't widen any existing bindings
488                for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) {
489                        i->allowWidening = false;
490                }
491                resultEnv.extractOpenVars( openVars );
492
493                // flatten actuals so that each actual has an atomic (non-tuple) type
494                AltList exploded;
495                Tuples::explode( actuals, indexer, back_inserter( exploded ) );
496
497                AltList::iterator actualExpr = exploded.begin();
498                AltList::iterator actualEnd = exploded.end();
499                for ( DeclarationWithType * formal : formals ) {
500                        // match flattened actuals with formal parameters - actuals will be grouped to match
501                        // with formals as appropriate
502                        Cost cost = Cost::zero;
503                        std::list< Expression * > newExprs;
504                        ObjectDecl * obj = strict_dynamic_cast< ObjectDecl * >( formal );
505                        if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) {
506                                deleteAll( newExprs );
507                                return false;
508                        }
509                        // success - produce argument as a new alternative
510                        assert( newExprs.size() == 1 );
511                        out.push_back( Alternative( newExprs.front(), resultEnv, cost ) );
512                }
513                if ( actualExpr != actualEnd ) {
514                        // there are still actuals remaining, but we've run out of formal parameters to match against
515                        // this is okay only if the function is variadic
516                        if ( ! isVarArgs ) {
517                                return false;
518                        }
519                        out.splice( out.end(), exploded, actualExpr, actualEnd );
520                }
521                return true;
522        }
523
524        // /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
525        //typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;
526
527        static const int recursionLimit = /*10*/ 4;  ///< Limit to depth of recursion satisfaction
528        //static const unsigned recursionParentLimit = 1;  ///< Limit to the number of times an assertion can recursively use itself
529
530        void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
531                for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
532                        if ( i->second.isUsed ) {
533                                indexer.addId( i->first );
534                        }
535                }
536        }
537
538        template< typename ForwardIterator, typename OutputIterator >
539        void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /*const AssertionParentSet &needParents,*/
540                                                 int level, const SymTab::Indexer &indexer, OutputIterator out ) {
541                if ( begin == end ) {
542                        if ( newNeed.empty() ) {
543                                PRINT(
544                                        std::cerr << "all assertions satisfied, output alternative: ";
545                                        newAlt.print( std::cerr );
546                                        std::cerr << std::endl;
547                                );
548                                *out++ = newAlt;
549                                return;
550                        } else if ( level >= recursionLimit ) {
551                                throw SemanticError( "Too many recursive assertions" );
552                        } else {
553                                AssertionSet newerNeed;
554                                PRINT(
555                                        std::cerr << "recursing with new set:" << std::endl;
556                                        printAssertionSet( newNeed, std::cerr, 8 );
557                                )
558                                inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /*needParents,*/ level+1, indexer, out );
559                                return;
560                        }
561                }
562
563                ForwardIterator cur = begin++;
564                if ( ! cur->second.isUsed ) {
565                        inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /*needParents,*/ level, indexer, out );
566                        return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
567                }
568                DeclarationWithType *curDecl = cur->first;
569
570                PRINT(
571                        std::cerr << "inferRecursive: assertion is ";
572                        curDecl->print( std::cerr );
573                        std::cerr << std::endl;
574                )
575                std::list< DeclarationWithType* > candidates;
576                decls.lookupId( curDecl->get_name(), candidates );
577///   if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
578                for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {
579                        PRINT(
580                                std::cerr << "inferRecursive: candidate is ";
581                                (*candidate)->print( std::cerr );
582                                std::cerr << std::endl;
583                        )
584
585                        AssertionSet newHave, newerNeed( newNeed );
586                        TypeEnvironment newEnv( newAlt.env );
587                        OpenVarSet newOpenVars( openVars );
588                        Type *adjType = (*candidate)->get_type()->clone();
589                        adjustExprType( adjType, newEnv, indexer );
590                        adjType->accept( global_renamer );
591                        PRINT(
592                                std::cerr << "unifying ";
593                                curDecl->get_type()->print( std::cerr );
594                                std::cerr << " with ";
595                                adjType->print( std::cerr );
596                                std::cerr << std::endl;
597                        )
598                        if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
599                                PRINT(
600                                        std::cerr << "success!" << std::endl;
601                                )
602                                SymTab::Indexer newDecls( decls );
603                                addToIndexer( newHave, newDecls );
604                                Alternative newerAlt( newAlt );
605                                newerAlt.env = newEnv;
606                                assert( (*candidate)->get_uniqueId() );
607                                DeclarationWithType *candDecl = static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );
608
609                                // everything with an empty idChain was pulled in by the current assertion.
610                                // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
611                                for ( auto & a : newerNeed ) {
612                                        if ( a.second.idChain.empty() ) {
613                                                a.second.idChain = cur->second.idChain;
614                                                a.second.idChain.push_back( curDecl->get_uniqueId() );
615                                        }
616                                }
617
618                                //AssertionParentSet newNeedParents( needParents );
619                                // skip repeatingly-self-recursive assertion satisfaction
620                                // DOESN'T WORK: grandchild nodes conflict with their cousins
621                                //if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
622                                Expression *varExpr = new VariableExpr( candDecl );
623                                delete varExpr->get_result();
624                                varExpr->set_result( adjType->clone() );
625                                PRINT(
626                                        std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
627                                        curDecl->print( std::cerr );
628                                        std::cerr << " with declaration " << (*candidate)->get_uniqueId() << " ";
629                                        (*candidate)->print( std::cerr );
630                                        std::cerr << std::endl;
631                                )
632                                ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr );
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 = &appExpr->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;
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, 8 );
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->has_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                                // xxx - this doesn't work at the moment, since inferParameters requires an ApplicationExpr as the alternative.
916                                // Once this works, it should be possible to infer parameters on a cast expression and specialize any function.
917
918                                // inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
919                                candidates.emplace_back( std::move( newAlt ) );
920                        } // if
921                } // for
922
923                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
924                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
925                // selects first based on argument cost, then on conversion cost.
926                AltList minArgCost;
927                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
928                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
929        }
930
931        void AlternativeFinder::visit( VirtualCastExpr * castExpr ) {
932                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
933                AlternativeFinder finder( indexer, env );
934                // don't prune here, since it's guaranteed all alternatives will have the same type
935                finder.findWithoutPrune( castExpr->get_arg() );
936                for ( Alternative & alt : finder.alternatives ) {
937                        alternatives.push_back( Alternative(
938                                new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
939                                alt.env, alt.cost ) );
940                }
941        }
942
943        void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
944                AlternativeFinder funcFinder( indexer, env );
945                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
946                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
947                        // 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
948                        std::unique_ptr<Expression> aggrExpr( agg->expr->clone() );
949                        Type * aggrType = aggrExpr->get_result();
950                        if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
951                                aggrType = aggrType->stripReferences();
952                                aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
953                        }
954                        // find member of the given type
955                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
956                                addAggMembers( structInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
957                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
958                                addAggMembers( unionInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
959                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
960                                addTupleMembers( tupleType, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
961                        } // if
962                } // for
963        }
964
965        void AlternativeFinder::visit( MemberExpr *memberExpr ) {
966                alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
967        }
968
969        void AlternativeFinder::visit( NameExpr *nameExpr ) {
970                std::list< DeclarationWithType* > declList;
971                indexer.lookupId( nameExpr->get_name(), declList );
972                PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
973                for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
974                        VariableExpr newExpr( *i, nameExpr->get_argName() );
975                        alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
976                        PRINT(
977                                std::cerr << "decl is ";
978                                (*i)->print( std::cerr );
979                                std::cerr << std::endl;
980                                std::cerr << "newExpr is ";
981                                newExpr.print( std::cerr );
982                                std::cerr << std::endl;
983                        )
984                        renameTypes( alternatives.back().expr );
985                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
986                } // for
987        }
988
989        void AlternativeFinder::visit( VariableExpr *variableExpr ) {
990                // not sufficient to clone here, because variable's type may have changed
991                // since the VariableExpr was originally created.
992                alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
993        }
994
995        void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
996                alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
997        }
998
999        void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
1000                if ( sizeofExpr->get_isType() ) {
1001                        Type * newType = sizeofExpr->get_type()->clone();
1002                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1003                } else {
1004                        // find all alternatives for the argument to sizeof
1005                        AlternativeFinder finder( indexer, env );
1006                        finder.find( sizeofExpr->get_expr() );
1007                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1008                        AltList winners;
1009                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1010                        if ( winners.size() != 1 ) {
1011                                throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
1012                        } // if
1013                        // return the lowest cost alternative for the argument
1014                        Alternative &choice = winners.front();
1015                        referenceToRvalueConversion( choice.expr );
1016                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1017                } // if
1018        }
1019
1020        void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
1021                if ( alignofExpr->get_isType() ) {
1022                        Type * newType = alignofExpr->get_type()->clone();
1023                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1024                } else {
1025                        // find all alternatives for the argument to sizeof
1026                        AlternativeFinder finder( indexer, env );
1027                        finder.find( alignofExpr->get_expr() );
1028                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1029                        AltList winners;
1030                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1031                        if ( winners.size() != 1 ) {
1032                                throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
1033                        } // if
1034                        // return the lowest cost alternative for the argument
1035                        Alternative &choice = winners.front();
1036                        referenceToRvalueConversion( choice.expr );
1037                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1038                } // if
1039        }
1040
1041        template< typename StructOrUnionType >
1042        void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1043                std::list< Declaration* > members;
1044                aggInst->lookup( name, members );
1045                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1046                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1047                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1048                                renameTypes( alternatives.back().expr );
1049                        } else {
1050                                assert( false );
1051                        }
1052                }
1053        }
1054
1055        void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
1056                AlternativeFinder funcFinder( indexer, env );
1057                // xxx - resolveTypeof?
1058                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1059                        addOffsetof( structInst, offsetofExpr->get_member() );
1060                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1061                        addOffsetof( unionInst, offsetofExpr->get_member() );
1062                }
1063        }
1064
1065        void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
1066                alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
1067        }
1068
1069        void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
1070                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
1071        }
1072
1073        void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
1074                // assume no polymorphism
1075                // assume no implicit conversions
1076                assert( function->get_parameters().size() == 1 );
1077                PRINT(
1078                        std::cerr << "resolvAttr: funcDecl is ";
1079                        funcDecl->print( std::cerr );
1080                        std::cerr << " argType is ";
1081                        argType->print( std::cerr );
1082                        std::cerr << std::endl;
1083                )
1084                if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1085                        alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
1086                        for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
1087                                alternatives.back().expr->set_result( (*i)->get_type()->clone() );
1088                        } // for
1089                } // if
1090        }
1091
1092        void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1093                // assume no 'pointer-to-attribute'
1094                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1095                assert( nameExpr );
1096                std::list< DeclarationWithType* > attrList;
1097                indexer.lookupId( nameExpr->get_name(), attrList );
1098                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1099                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1100                                // check if the type is function
1101                                if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1102                                        // assume exactly one parameter
1103                                        if ( function->get_parameters().size() == 1 ) {
1104                                                if ( attrExpr->get_isType() ) {
1105                                                        resolveAttr( *i, function, attrExpr->get_type(), env );
1106                                                } else {
1107                                                        AlternativeFinder finder( indexer, env );
1108                                                        finder.find( attrExpr->get_expr() );
1109                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1110                                                                if ( choice->expr->get_result()->size() == 1 ) {
1111                                                                        resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1112                                                                } // fi
1113                                                        } // for
1114                                                } // if
1115                                        } // if
1116                                } // if
1117                        } // for
1118                } else {
1119                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1120                                VariableExpr newExpr( *i );
1121                                alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
1122                                renameTypes( alternatives.back().expr );
1123                        } // for
1124                } // if
1125        }
1126
1127        void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1128                AlternativeFinder firstFinder( indexer, env );
1129                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1130                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1131                        AlternativeFinder secondFinder( indexer, first->env );
1132                        secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1133                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1134                                LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1135                                alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1136                        }
1137                }
1138        }
1139
1140        void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1141                // find alternatives for condition
1142                AlternativeFinder firstFinder( indexer, env );
1143                firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1144                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1145                        // find alternatives for true expression
1146                        AlternativeFinder secondFinder( indexer, first->env );
1147                        secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1148                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1149                                // find alterantives for false expression
1150                                AlternativeFinder thirdFinder( indexer, second->env );
1151                                thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1152                                for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1153                                        // unify true and false types, then infer parameters to produce new alternatives
1154                                        OpenVarSet openVars;
1155                                        AssertionSet needAssertions, haveAssertions;
1156                                        Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1157                                        Type* commonType = nullptr;
1158                                        if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1159                                                ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1160                                                newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1161                                                // convert both options to the conditional result type
1162                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1163                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1164                                                newAlt.expr = newExpr;
1165                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1166                                        } // if
1167                                } // for
1168                        } // for
1169                } // for
1170        }
1171
1172        void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1173                TypeEnvironment newEnv( env );
1174                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1175                AlternativeFinder secondFinder( indexer, newEnv );
1176                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1177                for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1178                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1179                } // for
1180                delete newFirstArg;
1181        }
1182
1183        void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1184                // resolve low and high, accept alternatives whose low and high types unify
1185                AlternativeFinder firstFinder( indexer, env );
1186                firstFinder.findWithAdjustment( rangeExpr->get_low() );
1187                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1188                        AlternativeFinder secondFinder( indexer, first->env );
1189                        secondFinder.findWithAdjustment( rangeExpr->get_high() );
1190                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1191                                OpenVarSet openVars;
1192                                AssertionSet needAssertions, haveAssertions;
1193                                Alternative newAlt( 0, second->env, first->cost + second->cost );
1194                                Type* commonType = nullptr;
1195                                if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1196                                        RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1197                                        newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1198                                        newAlt.expr = newExpr;
1199                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1200                                } // if
1201                        } // for
1202                } // for
1203        }
1204
1205        void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1206                std::list< AlternativeFinder > subExprAlternatives;
1207                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1208                std::list< AltList > possibilities;
1209                combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1210                for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1211                        std::list< Expression * > exprs;
1212                        makeExprList( *i, exprs );
1213
1214                        TypeEnvironment compositeEnv;
1215                        simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1216                        alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
1217                } // for
1218        }
1219
1220        void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1221                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1222        }
1223
1224        void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1225                alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1226        }
1227
1228        void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1229                AlternativeFinder finder( indexer, env );
1230                // don't prune here, since it's guaranteed all alternatives will have the same type
1231                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1232                finder.findWithoutPrune( ctorExpr->get_callExpr() );
1233                for ( Alternative & alt : finder.alternatives ) {
1234                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1235                }
1236        }
1237
1238        void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1239                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1240        }
1241
1242        void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1243                alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1244        }
1245
1246        void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1247                AlternativeFinder finder( indexer, env );
1248                finder.findWithAdjustment( unqExpr->get_expr() );
1249                for ( Alternative & alt : finder.alternatives ) {
1250                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1251                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1252                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1253                }
1254        }
1255
1256        void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1257                StmtExpr * newStmtExpr = stmtExpr->clone();
1258                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1259                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1260                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1261        }
1262
1263        void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
1264                // handle each option like a cast
1265                AltList candidates;
1266                PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
1267                // O(N^2) checks of d-types with e-types
1268                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1269                        Type * toType = resolveTypeof( initAlt.type, indexer );
1270                        SymTab::validateType( toType, &indexer );
1271                        adjustExprType( toType, env, indexer );
1272                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1273                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1274                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1275                        AlternativeFinder finder( indexer, env );
1276                        finder.targetType = toType;
1277                        finder.findWithAdjustment( initExpr->get_expr() );
1278                        for ( Alternative & alt : finder.get_alternatives() ) {
1279                                TypeEnvironment newEnv( alt.env );
1280                                AssertionSet needAssertions, haveAssertions;
1281                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
1282                                PRINT( std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl; )
1283                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1284                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1285                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1286                                // to.
1287                                int discardedValues = alt.expr->get_result()->size() - toType->size();
1288                                if ( discardedValues < 0 ) continue;
1289                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1290                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1291                                // unification run for side-effects
1292                                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??
1293
1294                                Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
1295                                if ( thisCost != Cost::infinity ) {
1296                                        // count one safe conversion for each value that is thrown away
1297                                        thisCost.incSafe( discardedValues );
1298                                        candidates.push_back( Alternative( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost ) );
1299                                }
1300                        }
1301                }
1302
1303                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1304                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1305                // selects first based on argument cost, then on conversion cost.
1306                AltList minArgCost;
1307                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1308                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1309        }
1310} // namespace ResolvExpr
1311
1312// Local Variables: //
1313// tab-width: 4 //
1314// mode: c++ //
1315// compile-command: "make install" //
1316// End: //
Note: See TracBrowser for help on using the repository browser.