source: src/ResolvExpr/AlternativeFinder.cc @ 326338ae

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 326338ae was 326338ae, checked in by Rob Schluntz <rschlunt@…>, 7 years ago

Copy function alternative before reference-to-rvalue conversion to prevent unwanted side-effects

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