source: src/ResolvExpr/AlternativeFinder.cc @ c93bc28

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

Minor cleanup, debug statements

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