source: src/ResolvExpr/AlternativeFinder.cc @ d1685588

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

Resolve anonymous conversions when the expression is reference-typed

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