source: src/ResolvExpr/AlternativeFinder.cc @ 7069652

//
// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// AlternativeFinder.cc --
//
// Author           : Richard C. Bilson
// Created On       : Sat May 16 23:52:08 2015
// Last Modified By : Peter A. Buhr
// Last Modified On : Fri Mar 17 09:14:17 2017
// Update Count     : 30
//

#include <list>
#include <iterator>
#include <algorithm>
#include <functional>
#include <cassert>
#include <unordered_map>
#include <utility>
#include <vector>

#include "AlternativeFinder.h"
#include "Alternative.h"
#include "Cost.h"
#include "typeops.h"
#include "Unify.h"
#include "RenameVars.h"
#include "SynTree/Type.h"
#include "SynTree/Declaration.h"
#include "SynTree/Expression.h"
#include "SynTree/Initializer.h"
#include "SynTree/Visitor.h"
#include "SymTab/Indexer.h"
#include "SymTab/Mangler.h"
#include "SynTree/TypeSubstitution.h"
#include "SymTab/Validate.h"
#include "Tuples/Tuples.h"
#include "Tuples/Explode.h"
#include "Common/utility.h"
#include "InitTweak/InitTweak.h"
#include "InitTweak/GenInit.h"
#include "ResolveTypeof.h"
#include "Resolver.h"

extern bool resolvep;
#define PRINT( text ) if ( resolvep ) { text }
//#define DEBUG_COST

namespace ResolvExpr {
        Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) {
                CastExpr *castToVoid = new CastExpr( expr );

                AlternativeFinder finder( indexer, env );
                finder.findWithAdjustment( castToVoid );

                // it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0
                // interpretations, an exception has already been thrown.
                assert( finder.get_alternatives().size() == 1 );
                CastExpr *newExpr = dynamic_cast< CastExpr* >( finder.get_alternatives().front().expr );
                assert( newExpr );
                env = finder.get_alternatives().front().env;
                return newExpr->get_arg()->clone();
        }

        Cost sumCost( const AltList &in ) {
                Cost total;
                for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
                        total += i->cost;
                }
                return total;
        }

        namespace {
                void printAlts( const AltList &list, std::ostream &os, int indent = 0 ) {
                        for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
                                i->print( os, indent );
                                os << std::endl;
                        }
                }

                void makeExprList( const AltList &in, std::list< Expression* > &out ) {
                        for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
                                out.push_back( i->expr->clone() );
                        }
                }

                struct PruneStruct {
                        bool isAmbiguous;
                        AltList::iterator candidate;
                        PruneStruct() {}
                        PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
                };

                /// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
                template< typename InputIterator, typename OutputIterator >
                void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out, const SymTab::Indexer &indexer ) {
                        // select the alternatives that have the minimum conversion cost for a particular set of result types
                        std::map< std::string, PruneStruct > selected;
                        for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
                                PruneStruct current( candidate );
                                std::string mangleName;
                                {
                                        Type * newType = candidate->expr->get_result()->clone();
                                        candidate->env.apply( newType );
                                        mangleName = SymTab::Mangler::mangle( newType );
                                        delete newType;
                                }
                                std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
                                if ( mapPlace != selected.end() ) {
                                        if ( candidate->cost < mapPlace->second.candidate->cost ) {
                                                PRINT(
                                                        std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
                                                )
                                                selected[ mangleName ] = current;
                                        } else if ( candidate->cost == mapPlace->second.candidate->cost ) {
                                                PRINT(
                                                        std::cerr << "marking ambiguous" << std::endl;
                                                )
                                                mapPlace->second.isAmbiguous = true;
                                        }
                                } else {
                                        selected[ mangleName ] = current;
                                }
                        }

                        PRINT(
                                std::cerr << "there are " << selected.size() << " alternatives before elimination" << std::endl;
                        )

                        // accept the alternatives that were unambiguous
                        for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
                                if ( ! target->second.isAmbiguous ) {
                                        Alternative &alt = *target->second.candidate;
                                        alt.env.applyFree( alt.expr->get_result() );
                                        *out++ = alt;
                                }
                        }
                }

                void renameTypes( Expression *expr ) {
                        expr->get_result()->accept( global_renamer );
                }
        }

        template< typename InputIterator, typename OutputIterator >
        void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
                while ( begin != end ) {
                        AlternativeFinder finder( indexer, env );
                        finder.findWithAdjustment( *begin );
                        // XXX  either this
                        //Designators::fixDesignations( finder, (*begin++)->get_argName() );
                        // or XXX this
                        begin++;
                        PRINT(
                                std::cerr << "findSubExprs" << std::endl;
                                printAlts( finder.alternatives, std::cerr );
                        )
                        *out++ = finder;
                }
        }

        AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
                : indexer( indexer ), env( env ) {
        }

        void AlternativeFinder::find( Expression *expr, bool adjust, bool prune ) {
                expr->accept( *this );
                if ( alternatives.empty() ) {
                        throw SemanticError( "No reasonable alternatives for expression ", expr );
                }
                for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
                        if ( adjust ) {
                                adjustExprType( i->expr->get_result(), i->env, indexer );
                        }
                }
                if ( prune ) {
                        PRINT(
                                std::cerr << "alternatives before prune:" << std::endl;
                                printAlts( alternatives, std::cerr );
                        )
                        AltList::iterator oldBegin = alternatives.begin();
                        pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ), indexer );
                        if ( alternatives.begin() == oldBegin ) {
                                std::ostringstream stream;
                                stream << "Can't choose between " << alternatives.size() << " alternatives for expression ";
                                expr->print( stream );
                                stream << "Alternatives are:";
                                AltList winners;
                                findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
                                printAlts( winners, stream, 8 );
                                throw SemanticError( stream.str() );
                        }
                        alternatives.erase( oldBegin, alternatives.end() );
                        PRINT(
                                std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
                        )
                }

                // Central location to handle gcc extension keyword, etc. for all expression types.
                for ( Alternative &iter: alternatives ) {
                        iter.expr->set_extension( expr->get_extension() );
                        iter.expr->location = expr->location;
                } // for
        }

        void AlternativeFinder::findWithAdjustment( Expression *expr, bool prune ) {
                find( expr, true, prune );
        }

        void AlternativeFinder::addAnonConversions( const Alternative & alt ) {
                // adds anonymous member interpretations whenever an aggregate value type is seen.
                Expression * expr = alt.expr->clone();
                std::unique_ptr< Expression > manager( expr ); // RAII for expr
                alt.env.apply( expr->get_result() );
                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( expr->get_result() ) ) {
                        NameExpr nameExpr( "" );
                        addAggMembers( structInst, expr, alt.cost+Cost( 0, 0, 1 ), alt.env, &nameExpr );
                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( expr->get_result() ) ) {
                        NameExpr nameExpr( "" );
                        addAggMembers( unionInst, expr, alt.cost+Cost( 0, 0, 1 ), alt.env, &nameExpr );
                } // if
        }

        template< typename StructOrUnionType >
        void AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
                // by this point, member must be a name expr
                NameExpr * nameExpr = safe_dynamic_cast< NameExpr * >( member );
                const std::string & name = nameExpr->get_name();
                std::list< Declaration* > members;
                aggInst->lookup( name, members );

                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
                                alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
                                renameTypes( alternatives.back().expr );
                                addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
                        } else {
                                assert( false );
                        }
                }
        }

        void AlternativeFinder::addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
                if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
                        // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
                        // xxx - this should be improved by memoizing the value of constant exprs
                        // during parsing and reusing that information here.
                        std::stringstream ss( constantExpr->get_constant()->get_value() );
                        int val;
                        std::string tmp;
                        if ( ss >> val && ! (ss >> tmp) ) {
                                if ( val >= 0 && (unsigned int)val < tupleType->size() ) {
                                        alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
                                } // if
                        } // if
                } else if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( member ) ) {
                        // xxx - temporary hack until 0/1 are int constants
                        if ( nameExpr->get_name() == "0" || nameExpr->get_name() == "1" ) {
                                std::stringstream ss( nameExpr->get_name() );
                                int val;
                                ss >> val;
                                alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
                        }
                } // if
        }

        void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
                alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
        }

        Cost computeConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
                ApplicationExpr *appExpr = safe_dynamic_cast< ApplicationExpr* >( alt.expr );
                PointerType *pointer = safe_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
                FunctionType *function = safe_dynamic_cast< FunctionType* >( pointer->get_base() );

                Cost convCost( 0, 0, 0 );
                std::list< DeclarationWithType* >& formals = function->get_parameters();
                std::list< DeclarationWithType* >::iterator formal = formals.begin();
                std::list< Expression* >& actuals = appExpr->get_args();

                for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
                        Type * actualType = (*actualExpr)->get_result();
                        PRINT(
                                std::cerr << "actual expression:" << std::endl;
                                (*actualExpr)->print( std::cerr, 8 );
                                std::cerr << "--- results are" << std::endl;
                                actualType->print( std::cerr, 8 );
                        )
                        Cost actualCost;
                        if ( formal == formals.end() ) {
                                if ( function->get_isVarArgs() ) {
                                        convCost += Cost( 1, 0, 0 );
                                        continue;
                                } else {
                                        return Cost::infinity;
                                }
                        }
                        Type * formalType = (*formal)->get_type();
                        PRINT(
                                std::cerr << std::endl << "converting ";
                                actualType->print( std::cerr, 8 );
                                std::cerr << std::endl << " to ";
                                formalType->print( std::cerr, 8 );
                        )
                        Cost newCost = conversionCost( actualType, formalType, indexer, alt.env );
                        PRINT(
                                std::cerr << std::endl << "cost is" << newCost << std::endl;
                        )

                        if ( newCost == Cost::infinity ) {
                                return newCost;
                        }
                        convCost += newCost;
                        actualCost += newCost;
                        if ( actualCost != Cost( 0, 0, 0 ) ) {
                                Type *newType = formalType->clone();
                                alt.env.apply( newType );
                                *actualExpr = new CastExpr( *actualExpr, newType );
                        }
                        convCost += Cost( 0, polyCost( formalType, alt.env, indexer ) + polyCost( actualType, alt.env, indexer ), 0 );
                        ++formal; // can't be in for-loop update because of the continue
                }
                if ( formal != formals.end() ) {
                        return Cost::infinity;
                }

                for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
                        PRINT(
                                std::cerr << std::endl << "converting ";
                                assert->second.actualType->print( std::cerr, 8 );
                                std::cerr << std::endl << " to ";
                                assert->second.formalType->print( std::cerr, 8 );
                        )
                        Cost newCost = conversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
                        PRINT(
                                std::cerr << std::endl << "cost of conversion is " << newCost << std::endl;
                        )
                        if ( newCost == Cost::infinity ) {
                                return newCost;
                        }
                        convCost += newCost;
                        convCost += Cost( 0, polyCost( assert->second.formalType, alt.env, indexer ) + polyCost( assert->second.actualType, alt.env, indexer ), 0 );
                }

                return convCost;
        }

        /// Adds type variables to the open variable set and marks their assertions
        void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
                for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
                        unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar };
                        for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
                                needAssertions[ *assert ].isUsed = true;
                        }
///     needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
                }
        }

        /// instantiate a single argument by matching actuals from [actualIt, actualEnd) against formalType,
        /// producing expression(s) in out and their total cost in cost.
        template< typename AltIterator, typename OutputIterator >
        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 ) {
                if ( TupleType * tupleType = dynamic_cast< TupleType * >( formalType ) ) {
                        // formalType is a TupleType - group actuals into a TupleExpr whose type unifies with the TupleType
                        std::list< Expression * > exprs;
                        for ( Type * type : *tupleType ) {
                                if ( ! instantiateArgument( type, defaultValue, actualIt, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( exprs ) ) ) {
                                        deleteAll( exprs );
                                        return false;
                                }
                        }
                        *out++ = new TupleExpr( exprs );
                } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
                        // xxx - mixing default arguments with variadic??
                        std::list< Expression * > exprs;
                        for ( ; actualIt != actualEnd; ++actualIt ) {
                                exprs.push_back( actualIt->expr->clone() );
                                cost += actualIt->cost;
                        }
                        Expression * arg = nullptr;
                        if ( exprs.size() == 1 && Tuples::isTtype( exprs.front()->get_result() ) ) {
                                // the case where a ttype value is passed directly is special, e.g. for argument forwarding purposes
                                // xxx - what if passing multiple arguments, last of which is ttype?
                                // xxx - what would happen if unify was changed so that unifying tuple types flattened both before unifying lists? then pass in TupleType(ttype) below.
                                arg = exprs.front();
                        } else {
                                arg = new TupleExpr( exprs );
                        }
                        assert( arg && arg->get_result() );
                        if ( ! unify( ttype, arg->get_result(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
                                return false;
                        }
                        *out++ = arg;
                } else if ( actualIt != actualEnd ) {
                        // both actualType and formalType are atomic (non-tuple) types - if they unify
                        // then accept actual as an argument, otherwise return false (fail to instantiate argument)
                        Expression * actual = actualIt->expr;
                        Type * actualType = actual->get_result();
                        PRINT(
                                std::cerr << "formal type is ";
                                formalType->print( std::cerr );
                                std::cerr << std::endl << "actual type is ";
                                actualType->print( std::cerr );
                                std::cerr << std::endl;
                        )
                        if ( ! unify( formalType, actualType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
                                return false;
                        }
                        // move the expression from the alternative to the output iterator
                        *out++ = actual;
                        actualIt->expr = nullptr;
                        cost += actualIt->cost;
                        ++actualIt;
                } else {
                        // End of actuals - Handle default values
                        if ( SingleInit *si = dynamic_cast<SingleInit *>( defaultValue )) {
                                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( si->get_value() ) ) {
                                        // so far, only constant expressions are accepted as default values
                                        if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( castExpr->get_arg() ) ) {
                                                if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) ) {
                                                        if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
                                                                *out++ = cnstexpr->clone();
                                                                return true;
                                                        } // if
                                                } // if
                                        } // if
                                }
                        } // if
                        return false;
                } // if
                return true;
        }

        bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) {
                simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
                // make sure we don't widen any existing bindings
                for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) {
                        i->allowWidening = false;
                }
                resultEnv.extractOpenVars( openVars );

                // flatten actuals so that each actual has an atomic (non-tuple) type
                AltList exploded;
                Tuples::explode( actuals, indexer, back_inserter( exploded ) );

                AltList::iterator actualExpr = exploded.begin();
                AltList::iterator actualEnd = exploded.end();
                for ( DeclarationWithType * formal : formals ) {
                        // match flattened actuals with formal parameters - actuals will be grouped to match
                        // with formals as appropriate
                        Cost cost;
                        std::list< Expression * > newExprs;
                        ObjectDecl * obj = safe_dynamic_cast< ObjectDecl * >( formal );
                        if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) {
                                deleteAll( newExprs );
                                return false;
                        }
                        // success - produce argument as a new alternative
                        assert( newExprs.size() == 1 );
                        out.push_back( Alternative( newExprs.front(), resultEnv, cost ) );
                }
                if ( actualExpr != actualEnd ) {
                        // there are still actuals remaining, but we've run out of formal parameters to match against
                        // this is okay only if the function is variadic
                        if ( ! isVarArgs ) {
                                return false;
                        }
                        out.splice( out.end(), exploded, actualExpr, actualEnd );
                }
                return true;
        }

        // /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
        //typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;

        static const int recursionLimit = /*10*/ 4;  ///< Limit to depth of recursion satisfaction
        //static const unsigned recursionParentLimit = 1;  ///< Limit to the number of times an assertion can recursively use itself

        void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
                for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
                        if ( i->second.isUsed ) {
                                i->first->accept( indexer );
                        }
                }
        }

        template< typename ForwardIterator, typename OutputIterator >
        void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /*const AssertionParentSet &needParents,*/
                                                 int level, const SymTab::Indexer &indexer, OutputIterator out ) {
                if ( begin == end ) {
                        if ( newNeed.empty() ) {
                                PRINT(
                                        std::cerr << "all assertions satisfied, output alternative: ";
                                        newAlt.print( std::cerr );
                                        std::cerr << std::endl;
                                );
                                *out++ = newAlt;
                                return;
                        } else if ( level >= recursionLimit ) {
                                throw SemanticError( "Too many recursive assertions" );
                        } else {
                                AssertionSet newerNeed;
                                PRINT(
                                        std::cerr << "recursing with new set:" << std::endl;
                                        printAssertionSet( newNeed, std::cerr, 8 );
                                )
                                inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /*needParents,*/ level+1, indexer, out );
                                return;
                        }
                }

                ForwardIterator cur = begin++;
                if ( ! cur->second.isUsed ) {
                        inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /*needParents,*/ level, indexer, out );
                        return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
                }
                DeclarationWithType *curDecl = cur->first;

                PRINT(
                        std::cerr << "inferRecursive: assertion is ";
                        curDecl->print( std::cerr );
                        std::cerr << std::endl;
                )
                std::list< DeclarationWithType* > candidates;
                decls.lookupId( curDecl->get_name(), candidates );
///   if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
                for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {
                        PRINT(
                                std::cerr << "inferRecursive: candidate is ";
                                (*candidate)->print( std::cerr );
                                std::cerr << std::endl;
                        )

                        AssertionSet newHave, newerNeed( newNeed );
                        TypeEnvironment newEnv( newAlt.env );
                        OpenVarSet newOpenVars( openVars );
                        Type *adjType = (*candidate)->get_type()->clone();
                        adjustExprType( adjType, newEnv, indexer );
                        adjType->accept( global_renamer );
                        PRINT(
                                std::cerr << "unifying ";
                                curDecl->get_type()->print( std::cerr );
                                std::cerr << " with ";
                                adjType->print( std::cerr );
                                std::cerr << std::endl;
                        )
                        if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
                                PRINT(
                                        std::cerr << "success!" << std::endl;
                                )
                                SymTab::Indexer newDecls( decls );
                                addToIndexer( newHave, newDecls );
                                Alternative newerAlt( newAlt );
                                newerAlt.env = newEnv;
                                assert( (*candidate)->get_uniqueId() );
                                DeclarationWithType *candDecl = static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );

                                // everything with an empty idChain was pulled in by the current assertion.
                                // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
                                for ( auto & a : newerNeed ) {
                                        if ( a.second.idChain.empty() ) {
                                                a.second.idChain = cur->second.idChain;
                                                a.second.idChain.push_back( curDecl->get_uniqueId() );
                                        }
                                }

                                //AssertionParentSet newNeedParents( needParents );
                                // skip repeatingly-self-recursive assertion satisfaction
                                // DOESN'T WORK: grandchild nodes conflict with their cousins
                                //if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
                                Expression *varExpr = new VariableExpr( candDecl );
                                delete varExpr->get_result();
                                varExpr->set_result( adjType->clone() );
                                PRINT(
                                        std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
                                        curDecl->print( std::cerr );
                                        std::cerr << " with declaration " << (*candidate)->get_uniqueId() << " ";
                                        (*candidate)->print( std::cerr );
                                        std::cerr << std::endl;
                                )
                                ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr );
                                // 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).
                                InferredParams * inferParameters = &appExpr->get_inferParams();
                                for ( UniqueId id : cur->second.idChain ) {
                                        inferParameters = (*inferParameters)[ id ].inferParams.get();
                                }
                                // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
                                (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
                                inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /*newNeedParents,*/ level, indexer, out );
                        } else {
                                delete adjType;
                        }
                }
        }

        template< typename OutputIterator >
        void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
//      PRINT(
//          std::cerr << "inferParameters: assertions needed are" << std::endl;
//          printAll( need, std::cerr, 8 );
//          )
                SymTab::Indexer decls( indexer );
                PRINT(
                        std::cerr << "============= original indexer" << std::endl;
                        indexer.print( std::cerr );
                        std::cerr << "============= new indexer" << std::endl;
                        decls.print( std::cerr );
                )
                addToIndexer( have, decls );
                AssertionSet newNeed;
                //AssertionParentSet needParents;
                inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /*needParents,*/ 0, indexer, out );
//      PRINT(
//          std::cerr << "declaration 14 is ";
//          Declaration::declFromId
//          *out++ = newAlt;
//          )
        }

        template< typename OutputIterator >
        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) {
                OpenVarSet openVars;
                AssertionSet resultNeed, resultHave;
                TypeEnvironment resultEnv;
                makeUnifiableVars( funcType, openVars, resultNeed );
                AltList instantiatedActuals; // filled by instantiate function
                if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
                        // attempt to narrow based on expected target type
                        Type * returnType = funcType->get_returnVals().front()->get_type();
                        if ( ! unify( returnType, targetType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
                                // unification failed, don't pursue this alternative
                                return;
                        }
                }

                if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) {
                        ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
                        Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) );
                        makeExprList( instantiatedActuals, appExpr->get_args() );
                        PRINT(
                                std::cerr << "need assertions:" << std::endl;
                                printAssertionSet( resultNeed, std::cerr, 8 );
                        )
                        inferParameters( resultNeed, resultHave, newAlt, openVars, out );
                }
        }

        void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
                bool doneInit = false;
                AlternativeFinder funcOpFinder( indexer, env );

                AlternativeFinder funcFinder( indexer, env );

                {
                        std::string fname = InitTweak::getFunctionName( untypedExpr );
                        if ( fname == "&&" ) {
                                VoidType v = Type::Qualifiers();                // resolve to type void *
                                PointerType pt( Type::Qualifiers(), v.clone() );
                                UntypedExpr *vexpr = untypedExpr->clone();
                                vexpr->set_result( pt.clone() );
                                alternatives.push_back( Alternative( vexpr, env, Cost()) );
                                return;
                        }
                }

                funcFinder.findWithAdjustment( untypedExpr->get_function() );
                std::list< AlternativeFinder > argAlternatives;
                findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );

                std::list< AltList > possibilities;
                combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );

                // take care of possible tuple assignments
                // if not tuple assignment, assignment is taken care of as a normal function call
                Tuples::handleTupleAssignment( *this, untypedExpr, possibilities );

                AltList candidates;
                SemanticError errors;
                for ( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
                        try {
                                PRINT(
                                        std::cerr << "working on alternative: " << std::endl;
                                        func->print( std::cerr, 8 );
                                )
                                // check if the type is pointer to function
                                PointerType *pointer;
                                if ( ( pointer = dynamic_cast< PointerType* >( func->expr->get_result() ) ) ) {
                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
                                                for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
                                                        // XXX
                                                        //Designators::check_alternative( function, *actualAlt );
                                                        makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
                                                }
                                        } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( pointer->get_base() ) ) {
                                                EqvClass eqvClass;
                                                if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
                                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
                                                                for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
                                                                        makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
                                                                } // for
                                                        } // if
                                                } // if
                                        } // if
                                } else {
                                        // seek a function operator that's compatible
                                        if ( ! doneInit ) {
                                                doneInit = true;
                                                NameExpr *opExpr = new NameExpr( "?()" );
                                                try {
                                                        funcOpFinder.findWithAdjustment( opExpr );
                                                } catch( SemanticError &e ) {
                                                        // it's ok if there aren't any defined function ops
                                                }
                                                PRINT(
                                                        std::cerr << "known function ops:" << std::endl;
                                                        printAlts( funcOpFinder.alternatives, std::cerr, 8 );
                                                )
                                        }

                                        for ( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
                                                // check if the type is pointer to function
                                                PointerType *pointer;
                                                if ( ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result() ) ) ) {
                                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
                                                                for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
                                                                        AltList currentAlt;
                                                                        currentAlt.push_back( *func );
                                                                        currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
                                                                        makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) );
                                                                } // for
                                                        } // if
                                                } // if
                                        } // for
                                } // if
                        } catch ( SemanticError &e ) {
                                errors.append( e );
                        }
                } // for

                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }

                // compute conversionsion costs
                for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
                        Cost cvtCost = computeConversionCost( *withFunc, indexer );

                        PRINT(
                                ApplicationExpr *appExpr = safe_dynamic_cast< ApplicationExpr* >( withFunc->expr );
                                PointerType *pointer = safe_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
                                FunctionType *function = safe_dynamic_cast< FunctionType* >( pointer->get_base() );
                                std::cerr << "Case +++++++++++++" << std::endl;
                                std::cerr << "formals are:" << std::endl;
                                printAll( function->get_parameters(), std::cerr, 8 );
                                std::cerr << "actuals are:" << std::endl;
                                printAll( appExpr->get_args(), std::cerr, 8 );
                                std::cerr << "bindings are:" << std::endl;
                                withFunc->env.print( std::cerr, 8 );
                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
                        )
                        if ( cvtCost != Cost::infinity ) {
                                withFunc->cvtCost = cvtCost;
                                alternatives.push_back( *withFunc );
                        } // if
                } // for
                // function may return struct or union value, in which case we need to add alternatives for implicit conversions to each of the anonymous members
                for ( const Alternative & alt : alternatives ) {
                        addAnonConversions( alt );
                }

                candidates.clear();
                candidates.splice( candidates.end(), alternatives );

                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );

                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
                        //   const char * x = "hello world";
                        //   unsigned char ch = x[0];
                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
                        // fix this issue in a more robust way.
                        targetType = nullptr;
                        visit( untypedExpr );
                }
        }

        bool isLvalue( Expression *expr ) {
                // xxx - recurse into tuples?
                return expr->has_result() && expr->get_result()->get_lvalue();
        }

        void AlternativeFinder::visit( AddressExpr *addressExpr ) {
                AlternativeFinder finder( indexer, env );
                finder.find( addressExpr->get_arg() );
                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
                        if ( isLvalue( i->expr ) ) {
                                alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
                        } // if
                } // for
        }

        void AlternativeFinder::visit( CastExpr *castExpr ) {
                Type *& toType = castExpr->get_result();
                assert( toType );
                toType = resolveTypeof( toType, indexer );
                SymTab::validateType( toType, &indexer );
                adjustExprType( toType, env, indexer );

                AlternativeFinder finder( indexer, env );
                finder.targetType = toType;
                finder.findWithAdjustment( castExpr->get_arg() );

                AltList candidates;
                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
                        AssertionSet needAssertions, haveAssertions;
                        OpenVarSet openVars;

                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
                        // to.
                        int discardedValues = (*i).expr->get_result()->size() - castExpr->get_result()->size();
                        if ( discardedValues < 0 ) continue;
                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
                        // unification run for side-effects
                        unify( castExpr->get_result(), (*i).expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
                        Cost thisCost = castCost( (*i).expr->get_result(), castExpr->get_result(), indexer, i->env );
                        if ( thisCost != Cost::infinity ) {
                                // count one safe conversion for each value that is thrown away
                                thisCost += Cost( 0, 0, discardedValues );

                                Expression * argExpr = i->expr->clone();
                                if ( argExpr->get_result()->size() > 1 && ! castExpr->get_result()->isVoid() ) {
                                        // Argument expression is a tuple and the target type is not void. Cast each member of the tuple
                                        // to its corresponding target type, producing the tuple of those cast expressions. If there are
                                        // more components of the tuple than components in the target type, then excess components do not
                                        // come out in the result expression (but UniqueExprs ensure that side effects will still be done).
                                        if ( Tuples::maybeImpure( argExpr ) && ! dynamic_cast< UniqueExpr * >( argExpr ) ) {
                                                // expressions which may contain side effects require a single unique instance of the expression.
                                                argExpr = new UniqueExpr( argExpr );
                                        }
                                        std::list< Expression * > componentExprs;
                                        for ( unsigned int i = 0; i < castExpr->get_result()->size(); i++ ) {
                                                // cast each component
                                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
                                                componentExprs.push_back( new CastExpr( idx, castExpr->get_result()->getComponent( i )->clone() ) );
                                        }
                                        delete argExpr;
                                        assert( componentExprs.size() > 0 );
                                        // produce the tuple of casts
                                        candidates.push_back( Alternative( new TupleExpr( componentExprs ), i->env, i->cost, thisCost ) );
                                } else {
                                        // handle normally
                                        candidates.push_back( Alternative( new CastExpr( argExpr->clone(), toType->clone() ), i->env, i->cost, thisCost ) );
                                }
                        } // if
                } // for

                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
                // selects first based on argument cost, then on conversion cost.
                AltList minArgCost;
                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
        }

        void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
                AlternativeFinder funcFinder( indexer, env );
                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( agg->expr->get_result() ) ) {
                                addAggMembers( structInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( agg->expr->get_result() ) ) {
                                addAggMembers( unionInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( agg->expr->get_result() ) ) {
                                addTupleMembers( tupleType, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
                        } // if
                } // for
        }

        void AlternativeFinder::visit( MemberExpr *memberExpr ) {
                alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
        }

        void AlternativeFinder::visit( NameExpr *nameExpr ) {
                std::list< DeclarationWithType* > declList;
                indexer.lookupId( nameExpr->get_name(), declList );
                PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
                for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
                        VariableExpr newExpr( *i, nameExpr->get_argName() );
                        alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
                        PRINT(
                                std::cerr << "decl is ";
                                (*i)->print( std::cerr );
                                std::cerr << std::endl;
                                std::cerr << "newExpr is ";
                                newExpr.print( std::cerr );
                                std::cerr << std::endl;
                        )
                        renameTypes( alternatives.back().expr );
                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
                } // for
        }

        void AlternativeFinder::visit( VariableExpr *variableExpr ) {
                // not sufficient to clone here, because variable's type may have changed
                // since the VariableExpr was originally created.
                alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
        }

        void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
                alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
        }

        void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
                if ( sizeofExpr->get_isType() ) {
                        // xxx - resolveTypeof?
                        alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) );
                } else {
                        // find all alternatives for the argument to sizeof
                        AlternativeFinder finder( indexer, env );
                        finder.find( sizeofExpr->get_expr() );
                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
                        AltList winners;
                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
                        if ( winners.size() != 1 ) {
                                throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
                        } // if
                        // return the lowest cost alternative for the argument
                        Alternative &choice = winners.front();
                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
                } // if
        }

        void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
                if ( alignofExpr->get_isType() ) {
                        // xxx - resolveTypeof?
                        alternatives.push_back( Alternative( alignofExpr->clone(), env, Cost::zero ) );
                } else {
                        // find all alternatives for the argument to sizeof
                        AlternativeFinder finder( indexer, env );
                        finder.find( alignofExpr->get_expr() );
                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
                        AltList winners;
                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
                        if ( winners.size() != 1 ) {
                                throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
                        } // if
                        // return the lowest cost alternative for the argument
                        Alternative &choice = winners.front();
                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
                } // if
        }

        template< typename StructOrUnionType >
        void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
                std::list< Declaration* > members;
                aggInst->lookup( name, members );
                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
                                renameTypes( alternatives.back().expr );
                        } else {
                                assert( false );
                        }
                }
        }

        void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
                AlternativeFinder funcFinder( indexer, env );
                // xxx - resolveTypeof?
                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
                        addOffsetof( structInst, offsetofExpr->get_member() );
                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
                        addOffsetof( unionInst, offsetofExpr->get_member() );
                }
        }

        void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
                alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
        }

        void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
        }

        void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
                // assume no polymorphism
                // assume no implicit conversions
                assert( function->get_parameters().size() == 1 );
                PRINT(
                        std::cerr << "resolvAttr: funcDecl is ";
                        funcDecl->print( std::cerr );
                        std::cerr << " argType is ";
                        argType->print( std::cerr );
                        std::cerr << std::endl;
                )
                if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
                        alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
                        for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
                                alternatives.back().expr->set_result( (*i)->get_type()->clone() );
                        } // for
                } // if
        }

        void AlternativeFinder::visit( AttrExpr *attrExpr ) {
                // assume no 'pointer-to-attribute'
                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
                assert( nameExpr );
                std::list< DeclarationWithType* > attrList;
                indexer.lookupId( nameExpr->get_name(), attrList );
                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
                                // check if the type is function
                                if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
                                        // assume exactly one parameter
                                        if ( function->get_parameters().size() == 1 ) {
                                                if ( attrExpr->get_isType() ) {
                                                        resolveAttr( *i, function, attrExpr->get_type(), env );
                                                } else {
                                                        AlternativeFinder finder( indexer, env );
                                                        finder.find( attrExpr->get_expr() );
                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
                                                                if ( choice->expr->get_result()->size() == 1 ) {
                                                                        resolveAttr(*i, function, choice->expr->get_result(), choice->env );
                                                                } // fi
                                                        } // for
                                                } // if
                                        } // if
                                } // if
                        } // for
                } else {
                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
                                VariableExpr newExpr( *i );
                                alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
                                renameTypes( alternatives.back().expr );
                        } // for
                } // if
        }

        void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
                AlternativeFinder firstFinder( indexer, env );
                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
                        AlternativeFinder secondFinder( indexer, first->env );
                        secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
                                LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
                                alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
                        }
                }
        }

        void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
                // find alternatives for condition
                AlternativeFinder firstFinder( indexer, env );
                firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
                        // find alternatives for true expression
                        AlternativeFinder secondFinder( indexer, first->env );
                        secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
                                // find alterantives for false expression
                                AlternativeFinder thirdFinder( indexer, second->env );
                                thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
                                for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
                                        // unify true and false types, then infer parameters to produce new alternatives
                                        OpenVarSet openVars;
                                        AssertionSet needAssertions, haveAssertions;
                                        Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
                                        Type* commonType = nullptr;
                                        if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
                                                ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
                                                newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
                                                newAlt.expr = newExpr;
                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
                                        } // if
                                } // for
                        } // for
                } // for
        }

        void AlternativeFinder::visit( CommaExpr *commaExpr ) {
                TypeEnvironment newEnv( env );
                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
                AlternativeFinder secondFinder( indexer, newEnv );
                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
                for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
                } // for
                delete newFirstArg;
        }

        void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
                // resolve low and high, accept alternatives whose low and high types unify
                AlternativeFinder firstFinder( indexer, env );
                firstFinder.findWithAdjustment( rangeExpr->get_low() );
                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
                        AlternativeFinder secondFinder( indexer, first->env );
                        secondFinder.findWithAdjustment( rangeExpr->get_high() );
                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
                                OpenVarSet openVars;
                                AssertionSet needAssertions, haveAssertions;
                                Alternative newAlt( 0, second->env, first->cost + second->cost );
                                Type* commonType = nullptr;
                                if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
                                        RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
                                        newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
                                        newAlt.expr = newExpr;
                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
                                } // if
                        } // for
                } // for
        }

        void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
                std::list< AlternativeFinder > subExprAlternatives;
                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
                std::list< AltList > possibilities;
                combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
                for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
                        std::list< Expression * > exprs;
                        makeExprList( *i, exprs );

                        TypeEnvironment compositeEnv;
                        simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
                        alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
                } // for
        }

        void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
        }

        void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
                alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
        }

        void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
                AlternativeFinder finder( indexer, env );
                // don't prune here, since it's guaranteed all alternatives will have the same type
                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
                finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
                for ( Alternative & alt : finder.alternatives ) {
                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
                }
        }

        void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
        }

        void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
                alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
        }

        void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
                AlternativeFinder finder( indexer, env );
                finder.findWithAdjustment( unqExpr->get_expr() );
                for ( Alternative & alt : finder.alternatives ) {
                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
                }
        }

        void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
                StmtExpr * newStmtExpr = stmtExpr->clone();
                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
        }

} // namespace ResolvExpr

// Local Variables: //
// tab-width: 4 //
// mode: c++ //
// compile-command: "make install" //
// End: //