source: src/ResolvExpr/AlternativeFinder.cc @ 32b8144

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

resolve case labels and case ranges

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