source: src/ResolvExpr/AlternativeFinder.cc @ 64ac636

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

fix missing line numbers in some places, including member constructor generation

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