Changeset c0d00b6 for src/ResolvExpr

Timestamp:

Nov 25, 2017, 3:22:18 PM (8 years ago)

Author:

Rob Schluntz <rschlunt@…>

Branches:

ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum, stuck-waitfor-destruct

Children:

c6e2c18

Parents:

9d06142 (diff), 3de176d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' into cleanup-dtors

Location:

src/ResolvExpr

Files:

• Alternative.cc (modified) (2 diffs)
• Alternative.h (modified) (4 diffs)
• AlternativeFinder.cc (modified) (20 diffs)
• AlternativeFinder.h (modified) (3 diffs)
• ExplodedActual.cc (added)
• ExplodedActual.h (added)
• PtrsAssignable.cc (modified) (1 diff)
• RenameVars.cc (modified) (3 diffs)
• RenameVars.h (modified) (1 diff)
• Resolver.cc (modified) (2 diffs)
• TypeEnvironment.cc (modified) (1 diff)
• TypeEnvironment.h (modified) (2 diffs)
• module.mk (modified) (1 diff)
• typeops.h (modified) (3 diffs)

src/ResolvExpr/Alternative.cc

@@ -18 +18 @@
 #include <ostream>                       // for operator<<, ostream, basic_o...
 #include <string>                        // for operator<<, char_traits, string
+#include <utility>                       // for move
 
 #include "Common/utility.h"              // for maybeClone
@@ -81 +82 @@
                 os << std::endl;
         }
+
+        void splice( AltList& dst, AltList& src ) {
+                dst.reserve( dst.size() + src.size() );
+                for ( Alternative& alt : src ) {
+                        dst.push_back( std::move(alt) );
+                }
+                src.clear();
+        }
+
+        void spliceBegin( AltList& dst, AltList& src ) {
+                splice( src, dst );
+                dst.swap( src );
+        }
+
 } // namespace ResolvExpr
 

src/ResolvExpr/Alternative.h

@@ -17 +17 @@
 
 #include <iosfwd>             // for ostream
-#include <list>               // for list
+#include <vector>             // for vector
 
 #include "Cost.h"             // for Cost
@@ -25 +25 @@
 
 namespace ResolvExpr {
-        struct Alternative;
-
-        typedef std::list< Alternative > AltList;
-
         struct Alternative {
                 Alternative();
@@ -41 +37 @@
                 void print( std::ostream &os, Indenter indent = {} ) const;
 
+                /// Returns the stored expression, but released from management of this Alternative
+                Expression* release_expr() {
+                        Expression* tmp = expr;
+                        expr = nullptr;
+                        return tmp;
+                }
+
                 Cost cost;
                 Cost cvtCost;
@@ -46 +49 @@
                 TypeEnvironment env;
         };
+
+        typedef std::vector< Alternative > AltList;
+
+        /// Moves all elements from src to the end of dst
+        void splice( AltList& dst, AltList& src );
+
+        /// Moves all elements from src to the beginning of dst
+        void spliceBegin( AltList& dst, AltList& src );
 } // namespace ResolvExpr
 

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
 
 #include "Alternative.h"           // for AltList, Alternative
@@ -28 +30 @@
 #include "Common/utility.h"        // for deleteAll, printAll, CodeLocation
 #include "Cost.h"                  // for Cost, Cost::zero, operator<<, Cost...
+#include "ExplodedActual.h"        // for ExplodedActual
 #include "InitTweak/InitTweak.h"   // for getFunctionName
 #include "RenameVars.h"            // for RenameVars, global_renamer
@@ -49 +52 @@
 #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 {
@@ -178 +187 @@
                 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 );
                 }
@@ -186 +198 @@
                                 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;
@@ -198 +210 @@
                                 throw SemanticError( stream.str() );
                         }
-                        alternatives.erase( oldBegin, alternatives.end() );
+                        alternatives = move(pruned);
                         PRINT(
                                 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
@@ -333 +345 @@
                 tmpCost.incPoly( -tmpCost.get_polyCost() );
                 if ( tmpCost != Cost::zero ) {
-                // if ( convCost != Cost::zero ) {
                         Type *newType = formalType->clone();
                         env.apply( newType );
@@ -405 +416 @@
 ///     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 ) ) {
-                                // std::cerr << "unify failed" << std::endl;
-                                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 = Cost::zero;
-                        std::list< Expression * > newExprs;
-                        ObjectDecl * obj = strict_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;
         }
 
@@ -675 +570 @@
         }
 
-        template< typename OutputIterator >
-        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) {
-                OpenVarSet openVars;
-                AssertionSet resultNeed, resultHave;
-                TypeEnvironment resultEnv( func.env );
-                makeUnifiableVars( funcType, openVars, resultNeed );
-                resultEnv.add( funcType->get_forall() ); // add all type variables as open variables now so that those not used in the parameter list are still considered open
-                AltList instantiatedActuals; // filled by instantiate function
+        /// Gets a default value from an initializer, nullptr if not present
+        ConstantExpr* getDefaultValue( Initializer* init ) {
+                if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) {
+                        if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->get_value() ) ) {
+                                return dynamic_cast<ConstantExpr*>( ce->get_arg() );
+                        }
+                }
+                return nullptr;
+        }
+
+        /// State to iteratively build a match of parameter expressions to arguments
+        struct ArgPack {
+                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
+                unsigned nextExpl;                 ///< Index of next exploded element
+                unsigned explAlt;                  ///< Index of alternative for nextExpl > 0
+
+                ArgPack()
+                        : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
+
+                          tupleStart(0), nextExpl(0), explAlt(0) {}
+
+                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
+                                const OpenVarSet& openVars)
+                        : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
+                          openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
+
+                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
+                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
+                                unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
+                                unsigned explAlt = 0 )
+                        : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
+                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
+                          nextExpl(nextExpl), explAlt(explAlt) {}
+
+                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), nextExpl(0), explAlt(0) {}
+
+                /// true iff this pack is in the middle of an exploded argument
+                bool hasExpl() const { return nextExpl > 0; }
+
+                /// Gets the list of exploded alternatives for this pack
+                const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
+                        return args[nextArg-1][explAlt];
+                }
+
+                /// Ends a tuple expression, consolidating the appropriate actuals
+                void endTuple( const std::vector<ArgPack>& packs ) {
+                        // add all expressions in tuple to list, summing cost
+                        std::list<Expression*> exprs;
+                        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;
+                }
+        };
+
+        /// Instantiates an argument to match a formal, returns false if no results left
+        bool instantiateArgument( Type* formalType, Initializer* initializer,
+                        const ExplodedArgs& 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
+                        ++nTuples;
+                        for ( Type* type : *tupleType ) {
+                                // xxx - dropping initializer changes behaviour from previous, but seems correct
+                                if ( ! instantiateArgument(
+                                                type, nullptr, args, results, genStart, indexer, nTuples ) )
+                                        return false;
+                                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??
+
+                        // completed tuples; will be spliced to end of results to finish
+                        std::vector<ArgPack> finalResults{};
+
+                        // iterate until all results completed
+                        std::size_t genEnd;
+                        ++nTuples;
+                        do {
+                                genEnd = results.size();
+
+                                // add another argument to results
+                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
+                                        auto nextArg = results[i].nextArg;
+
+                                        // use next element of exploded tuple if present
+                                        if ( results[i].hasExpl() ) {
+                                                const ExplodedActual& expl = results[i].getExpl( args );
+
+                                                unsigned nextExpl = results[i].nextExpl + 1;
+                                                if ( nextExpl == expl.exprs.size() ) {
+                                                        nextExpl = 0;
+                                                }
+
+                                                results.emplace_back(
+                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
+                                                        copy(results[i].need), copy(results[i].have),
+                                                        copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
+                                                        results[i].explAlt );
+
+                                                continue;
+                                        }
+
+                                        // finish result when out of arguments
+                                        if ( nextArg >= args.size() ) {
+                                                ArgPack newResult{
+                                                        results[i].env, results[i].need, results[i].have,
+                                                        results[i].openVars };
+                                                newResult.nextArg = 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 ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
+                                                const ExplodedActual& expl = args[nextArg][j];
+
+                                                // fresh copies of parent parameters for this iteration
+                                                TypeEnvironment env = results[i].env;
+                                                OpenVarSet openVars = results[i].openVars;
+
+                                                env.addActual( expl.env, openVars );
+
+                                                // skip empty tuple arguments by (near-)cloning parent into next gen
+                                                if ( expl.exprs.empty() ) {
+                                                        results.emplace_back(
+                                                                results[i], move(env), copy(results[i].need),
+                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
+
+                                                        continue;
+                                                }
+
+                                                // add new result
+                                                results.emplace_back(
+                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
+                                                        copy(results[i].have), move(openVars), nextArg + 1,
+                                                        nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
+                                        }
+                                }
+
+                                // reset for next round
+                                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
+                std::size_t genEnd = results.size();
+                for ( std::size_t i = genStart; i < genEnd; ++i ) {
+                        auto nextArg = results[i].nextArg;
+
+                        // use remainder of exploded tuple if present
+                        if ( results[i].hasExpl() ) {
+                                const ExplodedActual& expl = results[i].getExpl( args );
+                                Expression* expr = expl.exprs[results[i].nextExpl].get();
+
+                                TypeEnvironment env = results[i].env;
+                                AssertionSet need = results[i].need, have = results[i].have;
+                                OpenVarSet openVars = results[i].openVars;
+
+                                Type* actualType = expr->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, env, need, have, openVars, indexer ) ) {
+                                        unsigned nextExpl = results[i].nextExpl + 1;
+                                        if ( nextExpl == expl.exprs.size() ) {
+                                                nextExpl = 0;
+                                        }
+
+                                        results.emplace_back(
+                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg,
+                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
+                                }
+
+                                continue;
+                        }
+
+                        // use default initializers if out of arguments
+                        if ( nextArg >= args.size() ) {
+                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
+                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
+                                                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), nextArg, nTuples );
+                                                }
+                                        }
+                                }
+
+                                continue;
+                        }
+
+                        // Check each possible next argument
+                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
+                                const ExplodedActual& expl = args[nextArg][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( expl.env, openVars );
+
+                                // skip empty tuple arguments by (near-)cloning parent into next gen
+                                if ( expl.exprs.empty() ) {
+                                        results.emplace_back(
+                                                results[i], move(env), move(need), move(have), move(openVars),
+                                                nextArg + 1, expl.cost );
+
+                                        continue;
+                                }
+
+                                // consider only first exploded actual
+                                Expression* expr = expl.exprs.front().get();
+                                Type* actualType = expr->get_result()->clone();
+
+                                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;
+                                )
+
+                                // attempt to unify types
+                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
+                                        // add new result
+                                        results.emplace_back(
+                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
+                                                nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
+                                }
+                        }
+                }
+
+                // reset for next parameter
+                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 );
+        }
+
+        template<typename OutputIterator>
+        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func,
+                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
+                OpenVarSet funcOpenVars;
+                AssertionSet funcNeed, funcHave;
+                TypeEnvironment funcEnv( func.env );
+                makeUnifiableVars( funcType, funcOpenVars, funcNeed );
+                // add all type variables as open variables now so that those not used in the parameter
+                // list are still considered open.
+                funcEnv.add( funcType->get_forall() );
+
                 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
+                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
+                                        indexer ) ) {
+                                // unification failed, don't pursue this function 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 << "instantiate function success: " << appExpr << std::endl;
-                                std::cerr << "need assertions:" << std::endl;
-                                printAssertionSet( resultNeed, std::cerr, 8 );
-                        )
-                        inferParameters( resultNeed, resultHave, newAlt, openVars, out );
+                // iteratively build matches, one parameter at a time
+                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, genStart, indexer ) )
+                                return;
+                }
+
+                if ( funcType->get_isVarArgs() ) {
+                        // 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 ) {
+                                        auto nextArg = results[i].nextArg;
+
+                                        // use remainder of exploded tuple if present
+                                        if ( results[i].hasExpl() ) {
+                                                const ExplodedActual& expl = results[i].getExpl( args );
+
+                                                unsigned nextExpl = results[i].nextExpl + 1;
+                                                if ( nextExpl == expl.exprs.size() ) {
+                                                        nextExpl = 0;
+                                                }
+
+                                                results.emplace_back(
+                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
+                                                        copy(results[i].need), copy(results[i].have),
+                                                        copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
+                                                        results[i].explAlt );
+
+                                                continue;
+                                        }
+
+                                        // finish result when out of arguments
+                                        if ( nextArg >= args.size() ) {
+                                                validateFunctionAlternative( func, results[i], results, out );
+
+                                                continue;
+                                        }
+
+                                        // add each possible next argument
+                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
+                                                const ExplodedActual& expl = args[nextArg][j];
+
+                                                // fresh copies of parent parameters for this iteration
+                                                TypeEnvironment env = results[i].env;
+                                                OpenVarSet openVars = results[i].openVars;
+
+                                                env.addActual( expl.env, openVars );
+
+                                                // skip empty tuple arguments by (near-)cloning parent into next gen
+                                                if ( expl.exprs.empty() ) {
+                                                        results.emplace_back(
+                                                                results[i], move(env), copy(results[i].need),
+                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
+
+                                                        continue;
+                                                }
+
+                                                // add new result
+                                                results.emplace_back(
+                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
+                                                        copy(results[i].have), move(openVars), nextArg + 1, 0,
+                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
+                                        }
+                                }
+
+                                genStart = genEnd;
+                        } while ( genEnd != results.size() );
+                } else {
+                        // filter out results that don't use all the arguments
+                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
+                                ArgPack& result = results[i];
+                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
+                                        validateFunctionAlternative( func, result, results, out );
+                                }
+                        }
                 }
         }
@@ -711 +1028 @@
                 if ( funcFinder.alternatives.empty() ) return;
 
-                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 ) );
+                std::vector< AlternativeFinder > argAlternatives;
+                findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
+                        back_inserter( argAlternatives ) );
 
                 // 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 );
+                Tuples::handleTupleAssignment( *this, untypedExpr, argAlternatives );
 
                 // find function operators
@@ -730 +1045 @@
                         printAlts( funcOpFinder.alternatives, std::cerr, 1 );
                 )
+
+                // pre-explode arguments
+                ExplodedArgs argExpansions;
+                argExpansions.reserve( argAlternatives.size() );
+
+                for ( const AlternativeFinder& arg : argAlternatives ) {
+                        argExpansions.emplace_back();
+                        auto& argE = argExpansions.back();
+                        argE.reserve( arg.alternatives.size() );
+
+                        for ( const Alternative& actual : arg ) {
+                                argE.emplace_back( actual, indexer );
+                        }
+                }
 
                 AltList candidates;
@@ -744 +1073 @@
                                                 Alternative newFunc( *func );
                                                 referenceToRvalueConversion( newFunc.expr );
-                                                for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
-                                                        // XXX
-                                                        //Designators::check_alternative( function, *actualAlt );
-                                                        makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) );
-                                                }
+                                                makeFunctionAlternatives( newFunc, function, argExpansions,
+                                                        std::back_inserter( candidates ) );
                                         }
                                 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
@@ -756 +1082 @@
                                                         Alternative newFunc( *func );
                                                         referenceToRvalueConversion( newFunc.expr );
-                                                        for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
-                                                                makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) );
-                                                        } // for
+                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
+                                                                std::back_inserter( candidates ) );
                                                 } // if
                                         } // if
                                 }
-
-                                // try each function operator ?() with the current function alternative and each of the argument combinations
-                                for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
-                                        // check if the type is pointer to function
-                                        if ( PointerType *pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result()->stripReferences() ) ) {
-                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
+                        } catch ( SemanticError &e ) {
+                                errors.append( e );
+                        }
+                } // for
+
+                // try each function operator ?() with each function alternative
+                if ( ! funcOpFinder.alternatives.empty() ) {
+                        // add exploded function alternatives to front of argument list
+                        std::vector<ExplodedActual> funcE;
+                        funcE.reserve( funcFinder.alternatives.size() );
+                        for ( const Alternative& actual : funcFinder ) {
+                                funcE.emplace_back( actual, indexer );
+                        }
+                        argExpansions.insert( argExpansions.begin(), move(funcE) );
+
+                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
+                                        funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
+                                try {
+                                        // check if type is a pointer to function
+                                        if ( PointerType* pointer = dynamic_cast<PointerType*>(
+                                                        funcOp->expr->get_result()->stripReferences() ) ) {
+                                                if ( FunctionType* function =
+                                                                dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
                                                         Alternative newFunc( *funcOp );
                                                         referenceToRvalueConversion( newFunc.expr );
-                                                        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( newFunc, function, currentAlt, std::back_inserter( candidates ) );
-                                                        } // for
-                                                } // if
-                                        } // if
-                                } // for
-                        } catch ( SemanticError &e ) {
-                                errors.append( e );
-                        }
-                } // for
+                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
+                                                                std::back_inserter( candidates ) );
+                                                }
+                                        }
+                                } catch ( SemanticError &e ) {
+                                        errors.append( e );
+                                }
+                        }
+                }
 
                 // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
@@ -788 +1126 @@
 
                 // 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() );
@@ -801 +1139 @@
                                 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 );
-
-                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
-
-                // 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
-                for ( const Alternative & alt : alternatives ) {
+                candidates = move(alternatives);
+
+                // use a new list so that alternatives are not examined by addAnonConversions twice.
+                AltList winners;
+                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 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 );
                 }
+                spliceBegin( alternatives, winners );
 
                 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
@@ -844 +1184 @@
                 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
@@ -852 +1193 @@
 
         void AlternativeFinder::visit( LabelAddressExpr * expr ) {
-                alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) );
+                alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
         }
 
@@ -894 +1235 @@
 
                 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;
@@ -902 +1243 @@
                         // 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
@@ -1200 +1553 @@
 
         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
         }

src/ResolvExpr/AlternativeFinder.h

@@ -21 +21 @@
 
 #include "Alternative.h"                 // for AltList, Alternative
+#include "ExplodedActual.h"              // for ExplodedActual
 #include "ResolvExpr/Cost.h"             // for Cost, Cost::infinity
 #include "ResolvExpr/TypeEnvironment.h"  // for AssertionSet, OpenVarSet
@@ -31 +32 @@
 
 namespace ResolvExpr {
+        struct ArgPack;
+
+        /// First index is which argument, second index is which alternative for that argument,
+        /// third index is which exploded element of that alternative
+        using ExplodedArgs = std::vector< std::vector< ExplodedActual > >;
+
         class AlternativeFinder : public Visitor {
           public:
                 AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env );
+
+                AlternativeFinder( const AlternativeFinder& o )
+                        : indexer(o.indexer), alternatives(o.alternatives), env(o.env),
+                          targetType(o.targetType) {}
+
+                AlternativeFinder( AlternativeFinder&& o )
+                        : indexer(o.indexer), alternatives(std::move(o.alternatives)), env(o.env),
+                          targetType(o.targetType) {}
+
+                AlternativeFinder& operator= ( const AlternativeFinder& o ) {
+                        if (&o == this) return *this;
+
+                        // horrific nasty hack to rebind references...
+                        alternatives.~AltList();
+                        new(this) AlternativeFinder(o);
+                        return *this;
+                }
+
+                AlternativeFinder& operator= ( AlternativeFinder&& o ) {
+                        if (&o == this) return *this;
+
+                        // horrific nasty hack to rebind references...
+                        alternatives.~AltList();
+                        new(this) AlternativeFinder(std::move(o));
+                        return *this;
+                }
+
                 void find( Expression *expr, bool adjust = false, bool prune = true, bool failFast = true );
                 /// Calls find with the adjust flag set; adjustment turns array and function types into equivalent pointer types
@@ -99 +133 @@
                 /// Adds alternatives for offsetof expressions, given the base type and name of the member
                 template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name );
-                bool instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out );
-                template< typename OutputIterator >
-                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out );
+                /// Takes a final result and checks if its assertions can be satisfied
+                template<typename OutputIterator>
+                void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out );
+                /// Finds matching alternatives for a function, given a set of arguments
+                template<typename OutputIterator>
+                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
+                /// Checks if assertion parameters match for a new alternative
                 template< typename OutputIterator >
                 void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );

src/ResolvExpr/PtrsAssignable.cc

@@ -68 +68 @@
 
         void PtrsAssignable::visit( __attribute((unused)) VoidType *voidType ) {
-                if ( ! dynamic_cast< FunctionType* >( dest ) ) {
-                        // T * = void * is safe for any T that is not a function type.
-                        // xxx - this should be unsafe...
-                        result = 1;
-                } // if
+                // T * = void * is disallowed - this is a change from C, where any
+                // void * can be assigned or passed to a non-void pointer without a cast.
         }
 

src/ResolvExpr/RenameVars.cc

@@ -29 +29 @@
         RenameVars global_renamer;
 
-        RenameVars::RenameVars() : level( 0 ) {
+        RenameVars::RenameVars() : level( 0 ), resetCount( 0 ) {
                 mapStack.push_front( std::map< std::string, std::string >() );
         }
@@ -35 +35 @@
         void RenameVars::reset() {
                 level = 0;
+                resetCount++;
         }
 
@@ -130 +131 @@
                         for ( Type::ForallList::iterator i = type->get_forall().begin(); i != type->get_forall().end(); ++i ) {
                                 std::ostringstream output;
-                                output << "_" << level << "_" << (*i)->get_name();
+                                output << "_" << resetCount << "_" << level << "_" << (*i)->get_name();
                                 std::string newname( output.str() );
                                 mapStack.front()[ (*i)->get_name() ] = newname;

src/ResolvExpr/RenameVars.h

@@ -48 +48 @@
                 void typeBefore( Type *type );
                 void typeAfter( Type *type );
-                int level;
+                int level, resetCount;
                 std::list< std::map< std::string, std::string > > mapStack;
         };

src/ResolvExpr/Resolver.cc

@@ -18 +18 @@
 #include <memory>                        // for allocator, allocator_traits<...
 #include <tuple>                         // for get
+#include <vector>
 
 #include "Alternative.h"                 // for Alternative, AltList
@@ -411 +412 @@
 
                         // Find all alternatives for all arguments in canonical form
-                        std::list< AlternativeFinder > argAlternatives;
+                        std::vector< AlternativeFinder > argAlternatives;
                         funcFinder.findSubExprs( clause.target.arguments.begin(), clause.target.arguments.end(), back_inserter( argAlternatives ) );
 
                         // List all combinations of arguments
-                        std::list< AltList > possibilities;
+                        std::vector< AltList > possibilities;
                         combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
 

src/ResolvExpr/TypeEnvironment.cc

@@ -201 +201 @@
         }
 
+        void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) {
+                for ( const EqvClass& c : actualEnv ) {
+                        EqvClass c2 = c;
+                        c2.allowWidening = false;
+                        for ( const std::string& var : c2.vars ) {
+                                openVars[ var ] = c2.data;
+                        }
+                        env.push_back( std::move(c2) );
+                }
+        }
+
+        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) {
+                env.print( out );
+                return out;
+        }
 } // namespace ResolvExpr
 

src/ResolvExpr/TypeEnvironment.h

@@ -86 +86 @@
                 TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
 
+                /// Iteratively adds the environment of a new actual (with allowWidening = false),
+                /// and extracts open variables.
+                void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
+
                 typedef std::list< EqvClass >::iterator iterator;
                 iterator begin() { return env.begin(); }
@@ -110 +114 @@
                 return sub.applyFree( type );
         }
+
+        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
 } // namespace ResolvExpr
 

src/ResolvExpr/module.mk

@@ -32 +32 @@
        ResolvExpr/Occurs.cc \
        ResolvExpr/TypeEnvironment.cc \
-       ResolvExpr/CurrentObject.cc
+       ResolvExpr/CurrentObject.cc \
+       ResolvExpr/ExplodedActual.cc

src/ResolvExpr/typeops.h

@@ -16 +16 @@
 #pragma once
 
+#include <vector>
+
 #include "SynTree/SynTree.h"
 #include "SynTree/Type.h"
@@ -28 +30 @@
         void combos( InputIterator begin, InputIterator end, OutputIterator out ) {
                 typedef typename InputIterator::value_type SetType;
-                typedef typename std::list< typename SetType::value_type > ListType;
+                typedef typename std::vector< typename SetType::value_type > ListType;
 
                 if ( begin == end )     {
@@ -38 +40 @@
                 begin++;
 
-                std::list< ListType > recursiveResult;
+                std::vector< ListType > recursiveResult;
                 combos( begin, end, back_inserter( recursiveResult ) );
 
-                for ( typename std::list< ListType >::const_iterator i = recursiveResult.begin(); i != recursiveResult.end(); ++i ) {
-                        for ( typename ListType::const_iterator j = current->begin(); j != current->end(); ++j ) {
-                                ListType result;
-                                std::back_insert_iterator< ListType > inserter = back_inserter( result );
-                                *inserter++ = *j;
-                                std::copy( i->begin(), i->end(), inserter );
-                                *out++ = result;
-                        } // for
-                } // for
+                for ( const auto& i : recursiveResult ) for ( const auto& j : *current ) {
+                        ListType result;
+                        std::back_insert_iterator< ListType > inserter = back_inserter( result );
+                        *inserter++ = j;
+                        std::copy( i.begin(), i.end(), inserter );
+                        *out++ = result;
+                }
         }