source: src/ResolvExpr/AlternativeFinder.cc @ 322b97e

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

Resolve typeof in sizeof/alignof expressions [fixes #37]

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