Changes in src/ResolvExpr/AlternativeFinder.cc [11094d9:83882e9]

File:

• src/ResolvExpr/AlternativeFinder.cc (modified) (21 diffs)

src/ResolvExpr/AlternativeFinder.cc

@@ -16 +16 @@
 #include <algorithm>               // for copy
 #include <cassert>                 // for strict_dynamic_cast, assert, assertf
+#include <cstddef>                 // for size_t
 #include <iostream>                // for operator<<, cerr, ostream, endl
 #include <iterator>                // for back_insert_iterator, back_inserter
 #include <list>                    // for _List_iterator, list, _List_const_...
 #include <map>                     // for _Rb_tree_iterator, map, _Rb_tree_c...
-#include <memory>                  // for allocator_traits<>::value_type
+#include <memory>                  // for allocator_traits<>::value_type, unique_ptr
 #include <utility>                 // for pair
 #include <vector>                  // for vector
@@ -50 +51 @@
 #define PRINT( text ) if ( resolvep ) { text }
 //#define DEBUG_COST
+
+using std::move;
+
+/// copies any copyable type
+template<typename T>
+T copy(const T& x) { return x; }
 
 namespace ResolvExpr {
@@ -179 +186 @@
                 expr->accept( *this );
                 if ( failFast && alternatives.empty() ) {
+                        PRINT(
+                                std::cerr << "No reasonable alternatives for expression " << expr << std::endl;
+                        )
                         throw SemanticError( "No reasonable alternatives for expression ", expr );
                 }
@@ -187 +197 @@
                                 printAlts( alternatives, std::cerr );
                         )
-                        AltList::iterator oldBegin = alternatives.begin();
-                        pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) );
-                        if ( failFast && alternatives.begin() == oldBegin ) {
+                        AltList pruned;
+                        pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) );
+                        if ( failFast && pruned.empty() ) {
                                 std::ostringstream stream;
                                 AltList winners;
@@ -199 +209 @@
                                 throw SemanticError( stream.str() );
                         }
-                        alternatives.erase( oldBegin, alternatives.end() );
+                        alternatives = move(pruned);
                         PRINT(
                                 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
@@ -571 +581 @@
         /// State to iteratively build a match of parameter expressions to arguments
         struct ArgPack {
-                AltList actuals;                 ///< Arguments included in this pack
-                TypeEnvironment env;             ///< Environment for this pack
-                AssertionSet need;               ///< Assertions outstanding for this pack
-                AssertionSet have;               ///< Assertions found for this pack
-                OpenVarSet openVars;             ///< Open variables for this pack
-                unsigned nextArg;                ///< Index of next argument in arguments list
-                std::vector<Alternative> expls;  ///< Exploded actuals left over from last match
-                unsigned nextExpl;               ///< Index of next exploded alternative to use
-                std::vector<unsigned> tupleEls;  /// Number of elements in current tuple element(s)
+                std::size_t parent;                ///< Index of parent pack
+                std::unique_ptr<Expression> expr;  ///< The argument stored here
+                Cost cost;                         ///< The cost of this argument
+                TypeEnvironment env;               ///< Environment for this pack
+                AssertionSet need;                 ///< Assertions outstanding for this pack
+                AssertionSet have;                 ///< Assertions found for this pack
+                OpenVarSet openVars;               ///< Open variables for this pack
+                unsigned nextArg;                  ///< Index of next argument in arguments list
+                unsigned tupleStart;               ///< Number of tuples that start at this index
+                // TODO fix this somehow
+                std::vector<Alternative> expls;    ///< Exploded actuals left over from last match
+
+                ArgPack()
+                        : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
+                          tupleStart(0), expls() {}
 
                 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
                                 const OpenVarSet& openVars)
-                        : actuals(), env(env), need(need), have(have), openVars(openVars), nextArg(0),
-                          expls(), nextExpl(0), tupleEls() {}
-
-                /// Starts a new tuple expression
-                void beginTuple() {
-                        if ( ! tupleEls.empty() ) ++tupleEls.back();
-                        tupleEls.push_back(0);
-                }
+                        : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
+                          openVars(openVars), nextArg(0), tupleStart(0), expls() {}
+
+                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
+                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
+                                unsigned tupleStart = 0, Cost cost = Cost::zero,
+                                std::vector<Alternative>&& expls = std::vector<Alternative>{} )
+                        : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
+                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
+                          expls(move(expls)) {}
+
+                ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
+                                OpenVarSet&& openVars, unsigned nextArg, Cost added )
+                        : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added),
+                          env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)),
+                          nextArg(nextArg), tupleStart(o.tupleStart), expls() {}
+
+
+                // ArgPack(const ArgPack& o)
+                //      : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), env(o.env),
+                //        need(o.need), have(o.have), openVars(o.openVars), nextArg(o.nextArg),
+                //        tupleStart(o.tupleStart), expls(o.expls) {}
+
+                // ArgPack(ArgPack&&) = default;
 
                 /// Ends a tuple expression, consolidating the appropriate actuals
-                void endTuple() {
-                        // set up new Tuple alternative
+                void endTuple( const std::vector<ArgPack>& packs ) {
+                        // add all expressions in tuple to list, summing cost
                         std::list<Expression*> exprs;
-                        Cost cost = Cost::zero;
-
-                        // transfer elements into alternative
-                        for (unsigned i = 0; i < tupleEls.back(); ++i) {
-                                exprs.push_front( actuals.back().expr );
-                                actuals.back().expr = nullptr;
-                                cost += actuals.back().cost;
-                                actuals.pop_back();
-                        }
-                        tupleEls.pop_back();
-
-                        // build new alternative
-                        actuals.emplace_back( new TupleExpr( exprs ), this->env, cost );
-                }
-
-                /// Clones and adds an actual, returns this
-                ArgPack& withArg( Expression* expr, Cost cost = Cost::zero ) {
-                        actuals.emplace_back( expr->clone(), this->env, cost );
-                        if ( ! tupleEls.empty() ) ++tupleEls.back();
-                        return *this;
+                        const ArgPack* pack = this;
+                        if ( expr ) { exprs.push_front( expr.release() ); }
+                        while ( pack->tupleStart == 0 ) {
+                                pack = &packs[pack->parent];
+                                exprs.push_front( pack->expr->clone() );
+                                cost += pack->cost;
+                        }
+                        // reset pack to appropriate tuple
+                        expr.reset( new TupleExpr( exprs ) );
+                        tupleStart = pack->tupleStart - 1;
+                        parent = pack->parent;
                 }
         };
@@ -621 +644 @@
         /// Instantiates an argument to match a formal, returns false if no results left
         bool instantiateArgument( Type* formalType, Initializer* initializer,
-                        const std::vector< AlternativeFinder >& args,
-                        std::vector<ArgPack>& results, std::vector<ArgPack>& nextResults,
-                        const SymTab::Indexer& indexer ) {
+                        const std::vector< AlternativeFinder >& args, std::vector<ArgPack>& results,
+                        std::size_t& genStart, const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
                 if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) {
                         // formalType is a TupleType - group actuals into a TupleExpr
-                        for ( ArgPack& result : results ) { result.beginTuple(); }
+                        ++nTuples;
                         for ( Type* type : *tupleType ) {
                                 // xxx - dropping initializer changes behaviour from previous, but seems correct
-                                if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) )
+                                if ( ! instantiateArgument(
+                                                type, nullptr, args, results, genStart, indexer, nTuples ) )
                                         return false;
-                        }
-                        for ( ArgPack& result : results ) { result.endTuple(); }
+                                nTuples = 0;
+                        }
+                        // re-consititute tuples for final generation
+                        for ( auto i = genStart; i < results.size(); ++i ) {
+                                results[i].endTuple( results );
+                        }
                         return true;
                 } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) {
                         // formalType is a ttype, consumes all remaining arguments
                         // xxx - mixing default arguments with variadic??
-                        std::vector<ArgPack> finalResults{};  /// list of completed tuples
-                        // start tuples
-                        for ( ArgPack& result : results ) {
-                                result.beginTuple();
-
-                                // use rest of exploded tuple if present
-                                while ( result.nextExpl < result.expls.size() ) {
-                                        const Alternative& actual = result.expls[result.nextExpl];
-                                        result.env.addActual( actual.env, result.openVars );
-                                        result.withArg( actual.expr );
-                                        ++result.nextExpl;
-                                }
-                        }
+
+                        // completed tuples; will be spliced to end of results to finish
+                        std::vector<ArgPack> finalResults{};
+
                         // iterate until all results completed
-                        while ( ! results.empty() ) {
+                        std::size_t genEnd;
+                        ++nTuples;
+                        do {
+                                genEnd = results.size();
+
                                 // add another argument to results
-                                for ( ArgPack& result : results ) {
-                                        // finish result when out of arguments
-                                        if ( result.nextArg >= args.size() ) {
-                                                Type* argType = result.actuals.back().expr->get_result();
-                                                if ( result.tupleEls.back() == 1 && Tuples::isTtype( argType ) ) {
-                                                        // 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.
-                                                        result.tupleEls.pop_back();
-                                                } else {
-                                                        // collapse leftover arguments into tuple
-                                                        result.endTuple();
-                                                        argType = result.actuals.back().expr->get_result();
-                                                }
-                                                // check unification for ttype before adding to final
-                                                if ( unify( ttype, argType, result.env, result.need, result.have,
-                                                                result.openVars, indexer ) ) {
-                                                        finalResults.push_back( std::move(result) );
-                                                }
+                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
+                                        // use remainder of exploded tuple if present
+                                        if ( ! results[i].expls.empty() ) {
+                                                const Alternative& actual = results[i].expls.front();
+
+                                                TypeEnvironment env = results[i].env;
+                                                OpenVarSet openVars = results[i].openVars;
+
+                                                env.addActual( actual.env, openVars );
+
+                                                std::vector<Alternative> newExpls(
+                                                        std::next( results[i].expls.begin() ), results[i].expls.end() );
+                                                results.emplace_back(
+                                                        i, actual.expr, move(env), copy(results[i].need),
+                                                        copy(results[i].have), move(openVars), results[i].nextArg, nTuples,
+                                                        Cost::zero, move(newExpls) );
+
                                                 continue;
                                         }
 
+                                        // finish result when out of arguments
+                                        if ( results[i].nextArg >= args.size() ) {
+                                                ArgPack newResult{
+                                                        results[i].env, results[i].need, results[i].have,
+                                                        results[i].openVars };
+                                                newResult.nextArg = results[i].nextArg;
+                                                Type* argType;
+
+                                                if ( nTuples > 0 ) {
+                                                        // first iteration, push empty tuple expression
+                                                        newResult.parent = i;
+                                                        std::list<Expression*> emptyList;
+                                                        newResult.expr.reset( new TupleExpr( emptyList ) );
+                                                        argType = newResult.expr->get_result();
+                                                } else {
+                                                        // clone result to collect tuple
+                                                        newResult.parent = results[i].parent;
+                                                        newResult.cost = results[i].cost;
+                                                        newResult.tupleStart = results[i].tupleStart;
+                                                        newResult.expr.reset( results[i].expr->clone() );
+                                                        argType = newResult.expr->get_result();
+
+                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
+                                                                // 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.
+                                                                --newResult.tupleStart;
+                                                        } else {
+                                                                // collapse leftover arguments into tuple
+                                                                newResult.endTuple( results );
+                                                                argType = newResult.expr->get_result();
+                                                        }
+                                                }
+
+                                                // check unification for ttype before adding to final
+                                                if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
+                                                                newResult.openVars, indexer ) ) {
+                                                        finalResults.push_back( move(newResult) );
+                                                }
+
+                                                continue;
+                                        }
+
                                         // add each possible next argument
-                                        for ( const Alternative& actual : args[result.nextArg] ) {
-                                                ArgPack aResult = result;  // copy to clone everything
-                                                // add details of actual to result
-                                                aResult.env.addActual( actual.env, aResult.openVars );
-                                                Cost cost = actual.cost;
+                                        auto j = results[i].nextArg;
+                                        for ( const Alternative& actual : args[j] ) {
+                                                // fresh copies of parent parameters for this iteration
+                                                TypeEnvironment env = results[i].env;
+                                                OpenVarSet openVars = results[i].openVars;
+
+                                                env.addActual( actual.env, openVars );
 
                                                 // explode argument
                                                 std::vector<Alternative> exploded;
                                                 Tuples::explode( actual, indexer, back_inserter( exploded ) );
-
-                                                // add exploded argument to tuple
-                                                for ( Alternative& aActual : exploded ) {
-                                                        aResult.withArg( aActual.expr, cost );
-                                                        cost = Cost::zero;
+                                                if ( exploded.empty() ) {
+                                                        // skip empty tuple arguments by (near-)cloning parent into next gen
+                                                        results.emplace_back(
+                                                                results[i], move(env), copy(results[i].need),
+                                                                copy(results[i].have), move(openVars), j + 1, actual.cost );
+
+                                                        continue;
                                                 }
-                                                ++aResult.nextArg;
-                                                nextResults.push_back( std::move(aResult) );
+
+                                                // trim first element from exploded
+                                                std::vector<Alternative> newExpls;
+                                                newExpls.reserve( exploded.size() - 1 );
+                                                for ( std::size_t i = 1; i < exploded.size(); ++i ) {
+                                                        newExpls.push_back( move(exploded[i]) );
+                                                }
+                                                // add new result
+                                                results.emplace_back(
+                                                        i, exploded.front().expr, move(env), copy(results[i].need),
+                                                        copy(results[i].have), move(openVars), results[i].nextArg + 1,
+                                                        nTuples, actual.cost, move(newExpls) );
                                         }
                                 }
 
                                 // reset for next round
-                                results.swap( nextResults );
-                                nextResults.clear();
-                        }
-                        results.swap( finalResults );
-                        return ! results.empty();
+                                genStart = genEnd;
+                                nTuples = 0;
+                        } while ( genEnd != results.size() );
+
+                        // splice final results onto results
+                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
+                                results.push_back( move(finalResults[i]) );
+                        }
+                        return ! finalResults.empty();
                 }
 
                 // iterate each current subresult
-                for ( unsigned iResult = 0; iResult < results.size(); ++iResult ) {
-                        ArgPack& result = results[iResult];
-
-                        if ( result.nextExpl < result.expls.size() ) {
-                                // use remainder of exploded tuple if present
-                                const Alternative& actual = result.expls[result.nextExpl];
-                                result.env.addActual( actual.env, result.openVars );
+                std::size_t genEnd = results.size();
+                for ( std::size_t i = genStart; i < genEnd; ++i ) {
+                        // use remainder of exploded tuple if present
+                        if ( ! results[i].expls.empty() ) {
+                                const Alternative& actual = results[i].expls.front();
+
+                                TypeEnvironment env = results[i].env;
+                                AssertionSet need = results[i].need, have = results[i].have;
+                                OpenVarSet openVars = results[i].openVars;
+
+                                env.addActual( actual.env, openVars );
                                 Type* actualType = actual.expr->get_result();
 
@@ -725 +812 @@
                                 )
 
-                                if ( unify( formalType, actualType, result.env, result.need, result.have,
-                                                result.openVars, indexer ) ) {
-                                        ++result.nextExpl;
-                                        nextResults.push_back( std::move(result.withArg( actual.expr )) );
+                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
+                                        std::vector<Alternative> newExpls(
+                                                std::next( results[i].expls.begin() ), results[i].expls.end() );
+                                        results.emplace_back(
+                                                i, actual.expr, move(env), move(need), move(have), move(openVars),
+                                                results[i].nextArg, nTuples, Cost::zero, move(newExpls) );;
                                 }
 
                                 continue;
-                        } else if ( result.nextArg >= args.size() ) {
-                                // use default initializers if out of arguments
+                        }
+
+                        // use default initializers if out of arguments
+                        if ( results[i].nextArg >= args.size() ) {
                                 if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
                                         if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
-                                                if ( unify( formalType, cnst->get_type(), result.env, result.need,
-                                                                result.have, result.openVars, indexer ) ) {
-                                                        nextResults.push_back( std::move(result.withArg( cnstExpr )) );
+                                                TypeEnvironment env = results[i].env;
+                                                AssertionSet need = results[i].need, have = results[i].have;
+                                                OpenVarSet openVars = results[i].openVars;
+
+                                                if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
+                                                                indexer ) ) {
+                                                        results.emplace_back(
+                                                                i, cnstExpr, move(env), move(need), move(have),
+                                                                move(openVars), results[i].nextArg, nTuples );
                                                 }
                                         }
                                 }
+
                                 continue;
                         }
 
                         // Check each possible next argument
-                        for ( const Alternative& actual : args[result.nextArg] ) {
-                                ArgPack aResult = result;  // copy to clone everything
-                                // add details of actual to result
-                                aResult.env.addActual( actual.env, aResult.openVars );
+                        auto j = results[i].nextArg;
+                        for ( const Alternative& actual : args[j] ) {
+                                // fresh copies of parent parameters for this iteration
+                                TypeEnvironment env = results[i].env;
+                                AssertionSet need = results[i].need, have = results[i].have;
+                                OpenVarSet openVars = results[i].openVars;
+
+                                env.addActual( actual.env, openVars );
 
                                 // explode argument
@@ -755 +857 @@
                                 Tuples::explode( actual, indexer, back_inserter( exploded ) );
                                 if ( exploded.empty() ) {
-                                        // skip empty tuple arguments
-                                        ++aResult.nextArg;
-                                        results.push_back( std::move(aResult) );
+                                        // skip empty tuple arguments by (near-)cloning parent into next gen
+                                        results.emplace_back(
+                                                results[i], move(env), move(need), move(have), move(openVars), j + 1,
+                                                actual.cost );
+
                                         continue;
                                 }
@@ -774 +878 @@
 
                                 // attempt to unify types
-                                if ( unify( formalType, actualType, aResult.env, aResult.need, aResult.have, aResult.openVars, indexer ) ) {
-                                        // add argument
-                                        aResult.withArg( aActual.expr, actual.cost );
-                                        ++aResult.nextArg;
-                                        if ( exploded.size() > 1 ) {
-                                                // other parts of tuple left over
-                                                aResult.expls = std::move( exploded );
-                                                aResult.nextExpl = 1;
+                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
+                                        // trim first element from exploded
+                                        std::vector<Alternative> newExpls;
+                                        newExpls.reserve( exploded.size() - 1 );
+                                        for ( std::size_t i = 1; i < exploded.size(); ++i ) {
+                                                newExpls.push_back( move(exploded[i]) );
                                         }
-                                        nextResults.push_back( std::move(aResult) );
+                                        // add new result
+                                        results.emplace_back(
+                                                i, aActual.expr, move(env), move(need), move(have), move(openVars),
+                                                j + 1, nTuples, actual.cost, move(newExpls) );
                                 }
                         }
@@ -789 +894 @@
 
                 // reset for next parameter
-                results.swap( nextResults );
-                nextResults.clear();
-
-                return ! results.empty();
+                genStart = genEnd;
+
+                return genEnd != results.size();
+        }
+
+        template<typename OutputIterator>
+        void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result,
+                        const std::vector<ArgPack>& results, OutputIterator out ) {
+                ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
+                // sum cost and accumulate actuals
+                std::list<Expression*>& args = appExpr->get_args();
+                Cost cost = Cost::zero;
+                const ArgPack* pack = &result;
+                while ( pack->expr ) {
+                        args.push_front( pack->expr->clone() );
+                        cost += pack->cost;
+                        pack = &results[pack->parent];
+                }
+                // build and validate new alternative
+                Alternative newAlt( appExpr, result.env, cost );
+                PRINT(
+                        std::cerr << "instantiate function success: " << appExpr << std::endl;
+                        std::cerr << "need assertions:" << std::endl;
+                        printAssertionSet( result.need, std::cerr, 8 );
+                )
+                inferParameters( result.need, result.have, newAlt, result.openVars, out );
         }
 
@@ -818 +945 @@
 
                 // iteratively build matches, one parameter at a time
-                std::vector<ArgPack> results{ ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } };
-                std::vector<ArgPack> nextResults{};
+                std::vector<ArgPack> results;
+                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
+                std::size_t genStart = 0;
+
                 for ( DeclarationWithType* formal : funcType->get_parameters() ) {
                         ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
                         if ( ! instantiateArgument(
-                                        obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) )
+                                        obj->get_type(), obj->get_init(), args, results, genStart, indexer ) )
                                 return;
                 }
 
-                // filter out results that don't use all the arguments, and aren't variadic
-                std::vector<ArgPack> finalResults{};
                 if ( funcType->get_isVarArgs() ) {
-                        for ( ArgPack& result : results ) {
-                                // use rest of exploded tuple if present
-                                while ( result.nextExpl < result.expls.size() ) {
-                                        const Alternative& actual = result.expls[result.nextExpl];
-                                        result.env.addActual( actual.env, result.openVars );
-                                        result.withArg( actual.expr );
-                                        ++result.nextExpl;
-                                }
-                        }
-
-                        while ( ! results.empty() ) {
-                                // build combinations for all remaining arguments
-                                for ( ArgPack& result : results ) {
-                                        // keep if used all arguments
-                                        if ( result.nextArg >= args.size() ) {
-                                                finalResults.push_back( std::move(result) );
+                        // append any unused arguments to vararg pack
+                        std::size_t genEnd;
+                        do {
+                                genEnd = results.size();
+
+                                // iterate results
+                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
+                                        // use remainder of exploded tuple if present
+                                        if ( ! results[i].expls.empty() ) {
+                                                const Alternative& actual = results[i].expls.front();
+
+                                                TypeEnvironment env = results[i].env;
+                                                OpenVarSet openVars = results[i].openVars;
+
+                                                env.addActual( actual.env, openVars );
+
+                                                std::vector<Alternative> newExpls(
+                                                        std::next( results[i].expls.begin() ), results[i].expls.end() );
+                                                results.emplace_back(
+                                                        i, actual.expr, move(env), copy(results[i].need),
+                                                        copy(results[i].have), move(openVars), results[i].nextArg, 0,
+                                                        Cost::zero, move(newExpls) );
+
                                                 continue;
                                         }
 
+                                        // finish result when out of arguments
+                                        if ( results[i].nextArg >= args.size() ) {
+                                                validateFunctionAlternative( func, results[i], results, out );
+
+                                                continue;
+                                        }
+
                                         // add each possible next argument
-                                        for ( const Alternative& actual : args[result.nextArg] ) {
-                                                ArgPack aResult = result; // copy to clone everything
-                                                // add details of actual to result
-                                                aResult.env.addActual( actual.env, aResult.openVars );
-                                                Cost cost = actual.cost;
+                                        auto j = results[i].nextArg;
+                                        for ( const Alternative& actual : args[j] ) {
+                                                // fresh copies of parent parameters for this iteration
+                                                TypeEnvironment env = results[i].env;
+                                                OpenVarSet openVars = results[i].openVars;
+
+                                                env.addActual( actual.env, openVars );
 
                                                 // explode argument
                                                 std::vector<Alternative> exploded;
                                                 Tuples::explode( actual, indexer, back_inserter( exploded ) );
-
-                                                // add exploded argument to arg list
-                                                for ( Alternative& aActual : exploded ) {
-                                                        aResult.withArg( aActual.expr, cost );
-                                                        cost = Cost::zero;
+                                                if ( exploded.empty() ) {
+                                                        // skip empty tuple arguments by (near-)cloning parent into next gen
+                                                        results.emplace_back(
+                                                                results[i], move(env), copy(results[i].need),
+                                                                copy(results[i].have), move(openVars), j + 1, actual.cost );
+                                                        continue;
                                                 }
-                                                ++aResult.nextArg;
-                                                nextResults.push_back( std::move(aResult) );
+
+                                                // trim first element from exploded
+                                                std::vector<Alternative> newExpls;
+                                                newExpls.reserve( exploded.size() - 1 );
+                                                for ( std::size_t i = 1; i < exploded.size(); ++i ) {
+                                                        newExpls.push_back( move(exploded[i]) );
+                                                }
+                                                // add new result
+                                                results.emplace_back(
+                                                        i, exploded.front().expr, move(env), copy(results[i].need),
+                                                        copy(results[i].have), move(openVars), j + 1, 0,
+                                                        actual.cost, move(newExpls) );
                                         }
                                 }
 
-                                // reset for next round
-                                results.swap( nextResults );
-                                nextResults.clear();
-                        }
+                                genStart = genEnd;
+                        } while ( genEnd != results.size() );
                 } else {
                         // filter out results that don't use all the arguments
-                        for ( ArgPack& result : results ) {
-                                if ( result.nextExpl >= result.expls.size() && result.nextArg >= args.size() ) {
-                                        finalResults.push_back( std::move(result) );
+                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
+                                ArgPack& result = results[i];
+                                if ( result.expls.empty() && result.nextArg >= args.size() ) {
+                                        validateFunctionAlternative( func, result, results, out );
                                 }
                         }
-                }
-
-                // validate matching combos, add to final result list
-                for ( ArgPack& result : finalResults ) {
-                        ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
-                        Alternative newAlt( appExpr, result.env, sumCost( result.actuals ) );
-                        makeExprList( result.actuals, appExpr->get_args() );
-                        PRINT(
-                                std::cerr << "instantiate function success: " << appExpr << std::endl;
-                                std::cerr << "need assertions:" << std::endl;
-                                printAssertionSet( result.need, std::cerr, 8 );
-                        )
-                        inferParameters( result.need, result.have, newAlt, result.openVars, out );
                 }
         }
@@ -956 +1096 @@
                 if ( ! funcOpFinder.alternatives.empty() ) {
                         // add function alternatives to front of argument list
-                        argAlternatives.insert( argAlternatives.begin(), std::move(funcFinder) );
+                        argAlternatives.insert( argAlternatives.begin(), move(funcFinder) );
 
                         for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
@@ -982 +1122 @@
 
                 // compute conversionsion costs
-                for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
-                        Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer );
+                for ( Alternative& withFunc : candidates ) {
+                        Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
 
                         PRINT(
-                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc->expr );
+                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
                                 PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
                                 FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
@@ -995 +1135 @@
                                 printAll( appExpr->get_args(), std::cerr, 8 );
                                 std::cerr << "bindings are:" << std::endl;
-                                withFunc->env.print( std::cerr, 8 );
+                                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 );
+                                withFunc.cvtCost = cvtCost;
+                                alternatives.push_back( withFunc );
                         } // if
                 } // for
 
-                candidates.clear();
-                candidates.splice( candidates.end(), alternatives );
+                candidates = move(alternatives);
 
                 // use a new list so that alternatives are not examined by addAnonConversions twice.
@@ -1011 +1150 @@
                 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
 
-                // function may return struct or union value, in which case we need to add alternatives for implicit
-                // conversions to each of the anonymous members, must happen after findMinCost since anon conversions
-                // are never the cheapest expression
+                // function may return struct or union value, in which case we need to add alternatives
+                // for implicitconversions to each of the anonymous members, must happen after findMinCost
+                // since anon conversions are never the cheapest expression
                 for ( const Alternative & alt : winners ) {
                         addAnonConversions( alt );
                 }
-                alternatives.splice( alternatives.begin(), winners );
+                spliceBegin( alternatives, winners );
 
                 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
@@ -1041 +1180 @@
                 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 ) );
+                for ( Alternative& alt : finder.alternatives ) {
+                        if ( isLvalue( alt.expr ) ) {
+                                alternatives.push_back(
+                                        Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } );
                         } // if
                 } // for
@@ -1049 +1189 @@
 
         void AlternativeFinder::visit( LabelAddressExpr * expr ) {
-                alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) );
+                alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
         }
 
@@ -1091 +1231 @@
 
                 AltList candidates;
-                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
+                for ( Alternative & alt : finder.alternatives ) {
                         AssertionSet needAssertions, haveAssertions;
                         OpenVarSet openVars;
@@ -1099 +1239 @@
                         // 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();
+                        int discardedValues = alt.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 );
+                        unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions,
+                                haveAssertions, openVars, indexer );
+                        Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer,
+                                alt.env );
+                        PRINT(
+                                std::cerr << "working on cast with result: " << castExpr->result << std::endl;
+                                std::cerr << "and expr type: " << alt.expr->result << std::endl;
+                                std::cerr << "env: " << alt.env << std::endl;
+                        )
                         if ( thisCost != Cost::infinity ) {
+                                PRINT(
+                                        std::cerr << "has finite cost." << std::endl;
+                                )
                                 // count one safe conversion for each value that is thrown away
                                 thisCost.incSafe( discardedValues );
-                                Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost );
-                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
+                                Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env,
+                                        alt.cost, thisCost );
+                                inferParameters( needAssertions, haveAssertions, newAlt, openVars,
+                                        back_inserter( candidates ) );
                         } // if
                 } // for
@@ -1397 +1549 @@
 
         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::vector< AlternativeFinder > subExprAlternatives;
+                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
+                        back_inserter( subExprAlternatives ) );
+                std::vector< AltList > possibilities;
+                combos( subExprAlternatives.begin(), subExprAlternatives.end(),
+                        back_inserter( possibilities ) );
+                for ( const AltList& alts : possibilities ) {
                         std::list< Expression * > exprs;
-                        makeExprList( *i, exprs );
+                        makeExprList( alts, exprs );
 
                         TypeEnvironment compositeEnv;
-                        simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
-                        alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
+                        simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
+                        alternatives.push_back(
+                                Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
                 } // for
         }