source: src/ResolvExpr/AlternativeFinder.cc @ e6cee92

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

Fix TupleAssignment? code for references

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