source: src/ResolvExpr/AlternativeFinder.cc @ dd0c97b

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

fix inferred parameter data structures to correctly associate parameters with the entity that requested them, modify tuple specialization and unification to work with self-recursive assertions

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