source: src/ResolvExpr/AlternativeFinder.cc @ 74b007ba

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

Remove unused isDynamicLayout parameter from autogen, add some more debug information

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