source: src/ResolvExpr/AlternativeFinder.cc @ 89be1c68

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 89be1c68 was 89be1c68, checked in by Rob Schluntz <rschlunt@…>, 7 years ago

Remove Cost constructors, use only named members

This change makes it easier to read code involving costs, since in almost every case, only a single part of the cost tuple is relevant. Furthermore, this change makes it much simpler to add another dimension to the cost tuple, since only Cost.h needs to be updated, rather than every location using the cost constructor.

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