Changeset 403b388


Ignore:
Timestamp:
Nov 20, 2017, 2:07:19 PM (4 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
a94b829
Parents:
6d2386e
Message:

Tweaked resolver data structure to reduce dynamic allocation

Location:
src/ResolvExpr
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/AlternativeFinder.cc

    r6d2386e r403b388  
    1616#include <algorithm>               // for copy
    1717#include <cassert>                 // for strict_dynamic_cast, assert, assertf
     18#include <cstddef>                 // for size_t
    1819#include <iostream>                // for operator<<, cerr, ostream, endl
    1920#include <iterator>                // for back_insert_iterator, back_inserter
    2021#include <list>                    // for _List_iterator, list, _List_const_...
    2122#include <map>                     // for _Rb_tree_iterator, map, _Rb_tree_c...
    22 #include <memory>                  // for allocator_traits<>::value_type
     23#include <memory>                  // for allocator_traits<>::value_type, unique_ptr
    2324#include <utility>                 // for pair
    2425#include <vector>                  // for vector
     
    5051#define PRINT( text ) if ( resolvep ) { text }
    5152//#define DEBUG_COST
     53
     54using std::move;
     55
     56/// copies any copyable type
     57template<typename T>
     58T copy(const T& x) { return x; }
    5259
    5360namespace ResolvExpr {
     
    571578        /// State to iteratively build a match of parameter expressions to arguments
    572579        struct ArgPack {
    573                 AltList actuals;                 ///< Arguments included in this pack
    574                 TypeEnvironment env;             ///< Environment for this pack
    575                 AssertionSet need;               ///< Assertions outstanding for this pack
    576                 AssertionSet have;               ///< Assertions found for this pack
    577                 OpenVarSet openVars;             ///< Open variables for this pack
    578                 unsigned nextArg;                ///< Index of next argument in arguments list
    579                 std::vector<Alternative> expls;  ///< Exploded actuals left over from last match
    580                 unsigned nextExpl;               ///< Index of next exploded alternative to use
    581                 std::vector<unsigned> tupleEls;  /// Number of elements in current tuple element(s)
    582 
     580                std::size_t parent;                ///< Index of parent pack
     581                std::unique_ptr<Expression> expr;  ///< The argument stored here
     582                Cost cost;                         ///< The cost of this argument
     583                TypeEnvironment env;               ///< Environment for this pack
     584                AssertionSet need;                 ///< Assertions outstanding for this pack
     585                AssertionSet have;                 ///< Assertions found for this pack
     586                OpenVarSet openVars;               ///< Open variables for this pack
     587                unsigned nextArg;                  ///< Index of next argument in arguments list
     588                unsigned tupleStart;               ///< Number of tuples that start at this index
     589                // TODO fix this somehow
     590                std::vector<Alternative> expls;    ///< Exploded actuals left over from last match
     591
     592                ArgPack()
     593                        : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
     594                          tupleStart(0), expls() {}
     595               
    583596                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
    584597                                const OpenVarSet& openVars)
    585                         : actuals(), env(env), need(need), have(have), openVars(openVars), nextArg(0),
    586                           expls(), nextExpl(0), tupleEls() {}
     598                        : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
     599                          openVars(openVars), nextArg(0), tupleStart(0), expls() {}
    587600               
    588                 /// Starts a new tuple expression
    589                 void beginTuple() {
    590                         if ( ! tupleEls.empty() ) ++tupleEls.back();
    591                         tupleEls.push_back(0);
    592                 }
    593 
     601                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
     602                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
     603                                unsigned tupleStart = 0, Cost cost = Cost::zero,
     604                                std::vector<Alternative>&& expls = std::vector<Alternative>{} )
     605                        : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
     606                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
     607                          expls(move(expls)) {}
     608               
     609                // ArgPack(const ArgPack& o)
     610                //      : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), env(o.env),
     611                //        need(o.need), have(o.have), openVars(o.openVars), nextArg(o.nextArg),
     612                //        tupleStart(o.tupleStart), expls(o.expls) {}
     613
     614                // ArgPack(ArgPack&&) = default;
     615               
    594616                /// Ends a tuple expression, consolidating the appropriate actuals
    595                 void endTuple() {
    596                         // set up new Tuple alternative
     617                void endTuple( const std::vector<ArgPack>& packs ) {
     618                        // add all expressions in tuple to list, summing cost
    597619                        std::list<Expression*> exprs;
    598                         Cost cost = Cost::zero;
    599 
    600                         // transfer elements into alternative
    601                         for (unsigned i = 0; i < tupleEls.back(); ++i) {
    602                                 exprs.push_front( actuals.back().expr );
    603                                 actuals.back().expr = nullptr;
    604                                 cost += actuals.back().cost;
    605                                 actuals.pop_back();
    606                         }
    607                         tupleEls.pop_back();
    608 
    609                         // build new alternative
    610                         actuals.emplace_back( new TupleExpr( exprs ), this->env, cost );
    611                 }
    612 
    613                 /// Clones and adds an actual, returns this
    614                 ArgPack& withArg( Expression* expr, Cost cost = Cost::zero ) {
    615                         actuals.emplace_back( expr->clone(), this->env, cost );
    616                         if ( ! tupleEls.empty() ) ++tupleEls.back();
    617                         return *this;
     620                        const ArgPack* pack = this;
     621                        if ( expr ) { exprs.push_front( expr.release() ); }
     622                        while ( pack->tupleStart == 0 ) {
     623                                pack = &packs[pack->parent];
     624                                exprs.push_front( pack->expr->clone() );
     625                                cost += pack->cost;
     626                        }
     627                        // reset pack to appropriate tuple
     628                        expr.reset( new TupleExpr( exprs ) );
     629                        tupleStart = pack->tupleStart - 1;
     630                        parent = pack->parent;
    618631                }
    619632        };
     
    621634        /// Instantiates an argument to match a formal, returns false if no results left
    622635        bool instantiateArgument( Type* formalType, Initializer* initializer,
    623                         const std::vector< AlternativeFinder >& args,
    624                         std::vector<ArgPack>& results, std::vector<ArgPack>& nextResults,
    625                         const SymTab::Indexer& indexer ) {
     636                        const std::vector< AlternativeFinder >& args, std::vector<ArgPack>& results,
     637                        std::size_t& genStart, const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
    626638                if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) {
    627639                        // formalType is a TupleType - group actuals into a TupleExpr
    628                         for ( ArgPack& result : results ) { result.beginTuple(); }
     640                        ++nTuples;
    629641                        for ( Type* type : *tupleType ) {
    630642                                // xxx - dropping initializer changes behaviour from previous, but seems correct
    631                                 if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) )
     643                                if ( ! instantiateArgument(
     644                                                type, nullptr, args, results, genStart, indexer, nTuples ) )
    632645                                        return false;
    633                         }
    634                         for ( ArgPack& result : results ) { result.endTuple(); }
     646                                nTuples = 0;
     647                        }
     648                        // re-consititute tuples for final generation
     649                        for ( auto i = genStart; i < results.size(); ++i ) {
     650                                results[i].endTuple( results );
     651                        }
    635652                        return true;
    636653                } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) {
    637654                        // formalType is a ttype, consumes all remaining arguments
    638655                        // xxx - mixing default arguments with variadic??
    639                         std::vector<ArgPack> finalResults{};  /// list of completed tuples
    640                         // start tuples
    641                         for ( ArgPack& result : results ) {
    642                                 result.beginTuple();
    643 
    644                                 // use rest of exploded tuple if present
    645                                 while ( result.nextExpl < result.expls.size() ) {
    646                                         const Alternative& actual = result.expls[result.nextExpl];
    647                                         result.env.addActual( actual.env, result.openVars );
    648                                         result.withArg( actual.expr );
    649                                         ++result.nextExpl;
    650                                 }
    651                         }
     656
     657                        // completed tuples; will be spliced to end of results to finish
     658                        std::vector<ArgPack> finalResults{};
     659
    652660                        // iterate until all results completed
    653                         while ( ! results.empty() ) {
     661                        std::size_t genEnd;
     662                        ++nTuples;
     663                        do {
     664                                genEnd = results.size();
     665
    654666                                // add another argument to results
    655                                 for ( ArgPack& result : results ) {
    656                                         // finish result when out of arguments
    657                                         if ( result.nextArg >= args.size() ) {
    658                                                 Type* argType = result.actuals.back().expr->get_result();
    659                                                 if ( result.tupleEls.back() == 1 && Tuples::isTtype( argType ) ) {
    660                                                         // the case where a ttype value is passed directly is special, e.g. for
    661                                                         // argument forwarding purposes
    662                                                         // xxx - what if passing multiple arguments, last of which is ttype?
    663                                                         // xxx - what would happen if unify was changed so that unifying tuple
    664                                                         // types flattened both before unifying lists? then pass in TupleType
    665                                                         // (ttype) below.
    666                                                         result.tupleEls.pop_back();
    667                                                 } else {
    668                                                         // collapse leftover arguments into tuple
    669                                                         result.endTuple();
    670                                                         argType = result.actuals.back().expr->get_result();
    671                                                 }
    672                                                 // check unification for ttype before adding to final
    673                                                 if ( unify( ttype, argType, result.env, result.need, result.have,
    674                                                                 result.openVars, indexer ) ) {
    675                                                         finalResults.push_back( std::move(result) );
    676                                                 }
     667                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     668                                        // use remainder of exploded tuple if present
     669                                        if ( ! results[i].expls.empty() ) {
     670                                                const Alternative& actual = results[i].expls.front();
     671                                               
     672                                                TypeEnvironment env = results[i].env;
     673                                                OpenVarSet openVars = results[i].openVars;
     674
     675                                                env.addActual( actual.env, openVars );
     676
     677                                                std::vector<Alternative> newExpls(
     678                                                        std::next( results[i].expls.begin() ), results[i].expls.end() );
     679                                                results.emplace_back(
     680                                                        i, actual.expr, move(env), copy(results[i].need),
     681                                                        copy(results[i].have), move(openVars), results[i].nextArg, nTuples,
     682                                                        Cost::zero, move(newExpls) );
     683                                               
    677684                                                continue;
    678685                                        }
     686                                       
     687                                        // finish result when out of arguments
     688                                        if ( results[i].nextArg >= args.size() ) {
     689                                                ArgPack newResult{
     690                                                        results[i].env, results[i].need, results[i].have,
     691                                                        results[i].openVars };
     692                                                newResult.nextArg = results[i].nextArg;
     693                                                Type* argType;
     694
     695                                                if ( nTuples > 0 ) {
     696                                                        // first iteration, push empty tuple expression
     697                                                        newResult.parent = i;
     698                                                        std::list<Expression*> emptyList;
     699                                                        newResult.expr.reset( new TupleExpr( emptyList ) );
     700                                                        argType = newResult.expr->get_result();
     701                                                } else {
     702                                                        // clone result to collect tuple
     703                                                        newResult.parent = results[i].parent;
     704                                                        newResult.cost = results[i].cost;
     705                                                        newResult.tupleStart = results[i].tupleStart;
     706                                                        newResult.expr.reset( results[i].expr->clone() );
     707                                                        argType = newResult.expr->get_result();
     708
     709                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
     710                                                                // the case where a ttype value is passed directly is special,
     711                                                                // e.g. for argument forwarding purposes
     712                                                                // xxx - what if passing multiple arguments, last of which is
     713                                                                //       ttype?
     714                                                                // xxx - what would happen if unify was changed so that unifying
     715                                                                //       tuple
     716                                                                // types flattened both before unifying lists? then pass in
     717                                                                // TupleType (ttype) below.
     718                                                                --newResult.tupleStart;
     719                                                        } else {
     720                                                                // collapse leftover arguments into tuple
     721                                                                newResult.endTuple( results );
     722                                                                argType = newResult.expr->get_result();
     723                                                        }
     724                                                }
     725
     726                                                // check unification for ttype before adding to final
     727                                                if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
     728                                                                newResult.openVars, indexer ) ) {
     729                                                        finalResults.push_back( move(newResult) );
     730                                                }
     731                                               
     732                                                continue;
     733                                        }
    679734
    680735                                        // add each possible next argument
    681                                         for ( const Alternative& actual : args[result.nextArg] ) {
    682                                                 ArgPack aResult = result;  // copy to clone everything
    683                                                 // add details of actual to result
    684                                                 aResult.env.addActual( actual.env, aResult.openVars );
    685                                                 Cost cost = actual.cost;
    686                
     736                                        auto j = results[i].nextArg;
     737                                        for ( const Alternative& actual : args[j] ) {
     738                                                // fresh copies of parent parameters for this iteration
     739                                                TypeEnvironment env = results[i].env;
     740                                                OpenVarSet openVars = results[i].openVars;
     741
     742                                                env.addActual( actual.env, openVars );
     743
    687744                                                // explode argument
    688745                                                std::vector<Alternative> exploded;
    689746                                                Tuples::explode( actual, indexer, back_inserter( exploded ) );
    690                                                
    691                                                 // add exploded argument to tuple
    692                                                 for ( Alternative& aActual : exploded ) {
    693                                                         aResult.withArg( aActual.expr, cost );
    694                                                         cost = Cost::zero;
     747                                                if ( exploded.empty() ) {
     748                                                        // skip empty tuple arguments by (near-)cloning parent into next gen
     749                                                        results.emplace_back(
     750                                                                results[i].parent, results[i].expr.get(), move(env),
     751                                                                copy(results[i].need), copy(results[i].have), move(openVars),
     752                                                                j + 1, results[i].tupleStart, actual.cost + results[i].cost );
     753                                                        continue;
    695754                                                }
    696                                                 ++aResult.nextArg;
    697                                                 nextResults.push_back( std::move(aResult) );
     755
     756                                                // trim first element from exploded
     757                                                std::vector<Alternative> newExpls;
     758                                                newExpls.reserve( exploded.size() - 1 );
     759                                                for ( std::size_t i = 1; i < exploded.size(); ++i ) {
     760                                                        newExpls.push_back( move(exploded[i]) );
     761                                                }
     762                                                // add new result
     763                                                results.emplace_back(
     764                                                        i, actual.expr, move(env), copy(results[i].need),
     765                                                        copy(results[i].have), move(openVars), results[i].nextArg + 1,
     766                                                        nTuples, actual.cost, move(newExpls) );
    698767                                        }
    699768                                }
    700769
    701770                                // reset for next round
    702                                 results.swap( nextResults );
    703                                 nextResults.clear();
    704                         }
    705                         results.swap( finalResults );
    706                         return ! results.empty();
     771                                genStart = genEnd;
     772                                nTuples = 0;
     773                        } while ( genEnd != results.size() );
     774
     775                        // splice final results onto results
     776                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
     777                                results.push_back( move(finalResults[i]) );
     778                        }
     779                        return ! finalResults.empty();
    707780                }
    708781               
    709782                // iterate each current subresult
    710                 for ( unsigned iResult = 0; iResult < results.size(); ++iResult ) {
    711                         ArgPack& result = results[iResult];
    712 
    713                         if ( result.nextExpl < result.expls.size() ) {
    714                                 // use remainder of exploded tuple if present
    715                                 const Alternative& actual = result.expls[result.nextExpl];
    716                                 result.env.addActual( actual.env, result.openVars );
     783                std::size_t genEnd = results.size();
     784                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     785                        // use remainder of exploded tuple if present
     786                        if ( ! results[i].expls.empty() ) {
     787                                const Alternative& actual = results[i].expls.front();
     788                               
     789                                TypeEnvironment env = results[i].env;
     790                                AssertionSet need = results[i].need, have = results[i].have;
     791                                OpenVarSet openVars = results[i].openVars;
     792
     793                                env.addActual( actual.env, openVars );
    717794                                Type* actualType = actual.expr->get_result();
    718795
     
    725802                                )
    726803                               
    727                                 if ( unify( formalType, actualType, result.env, result.need, result.have,
    728                                                 result.openVars, indexer ) ) {
    729                                         ++result.nextExpl;
    730                                         nextResults.push_back( std::move(result.withArg( actual.expr )) );
     804                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
     805                                        std::vector<Alternative> newExpls(
     806                                                std::next( results[i].expls.begin() ), results[i].expls.end() );
     807                                        results.emplace_back(
     808                                                i, actual.expr, move(env), move(need), move(have), move(openVars),
     809                                                results[i].nextArg, nTuples, Cost::zero, move(newExpls) );;
    731810                                }
    732811
    733812                                continue;
    734                         } else if ( result.nextArg >= args.size() ) {
    735                                 // use default initializers if out of arguments
     813                        }
     814                       
     815                        // use default initializers if out of arguments
     816                        if ( results[i].nextArg >= args.size() ) {
    736817                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
    737818                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
    738                                                 if ( unify( formalType, cnst->get_type(), result.env, result.need,
    739                                                                 result.have, result.openVars, indexer ) ) {
    740                                                         nextResults.push_back( std::move(result.withArg( cnstExpr )) );
     819                                                TypeEnvironment env = results[i].env;
     820                                                AssertionSet need = results[i].need, have = results[i].have;
     821                                                OpenVarSet openVars = results[i].openVars;
     822
     823                                                if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
     824                                                                indexer ) ) {
     825                                                        results.emplace_back(
     826                                                                i, cnstExpr, move(env), move(need), move(have),
     827                                                                move(openVars), results[i].nextArg, nTuples );
    741828                                                }
    742829                                        }
    743830                                }
     831
    744832                                continue;
    745833                        }
    746834
    747835                        // Check each possible next argument
    748                         for ( const Alternative& actual : args[result.nextArg] ) {
    749                                 ArgPack aResult = result;  // copy to clone everything
    750                                 // add details of actual to result
    751                                 aResult.env.addActual( actual.env, aResult.openVars );
    752 
     836                        auto j = results[i].nextArg;
     837                        for ( const Alternative& actual : args[j] ) {
     838                                // fresh copies of parent parameters for this iteration
     839                                TypeEnvironment env = results[i].env;
     840                                AssertionSet need = results[i].need, have = results[i].have;
     841                                OpenVarSet openVars = results[i].openVars;
     842
     843                                env.addActual( actual.env, openVars );
     844                               
    753845                                // explode argument
    754846                                std::vector<Alternative> exploded;
    755847                                Tuples::explode( actual, indexer, back_inserter( exploded ) );
    756848                                if ( exploded.empty() ) {
    757                                         // skip empty tuple arguments
    758                                         ++aResult.nextArg;
    759                                         results.push_back( std::move(aResult) );
     849                                        // skip empty tuple arguments by (near-)cloning parent into next gen
     850                                        results.emplace_back(
     851                                                results[i].parent, results[i].expr.get(), move(env), move(need),
     852                                                move(have), move(openVars), j + 1, results[i].tupleStart,
     853                                                actual.cost + results[i].cost );
    760854                                        continue;
    761855                                }
     
    774868
    775869                                // attempt to unify types
    776                                 if ( unify( formalType, actualType, aResult.env, aResult.need, aResult.have, aResult.openVars, indexer ) ) {
    777                                         // add argument
    778                                         aResult.withArg( aActual.expr, actual.cost );
    779                                         ++aResult.nextArg;
    780                                         if ( exploded.size() > 1 ) {
    781                                                 // other parts of tuple left over
    782                                                 aResult.expls = std::move( exploded );
    783                                                 aResult.nextExpl = 1;
     870                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
     871                                        // trim first element from exploded
     872                                        std::vector<Alternative> newExpls;
     873                                        newExpls.reserve( exploded.size() - 1 );
     874                                        for ( std::size_t i = 1; i < exploded.size(); ++i ) {
     875                                                newExpls.push_back( move(exploded[i]) );
    784876                                        }
    785                                         nextResults.push_back( std::move(aResult) );
     877                                        // add new result
     878                                        results.emplace_back(
     879                                                i, aActual.expr, move(env), move(need), move(have), move(openVars),
     880                                                j + 1, nTuples, actual.cost, move(newExpls) );
    786881                                }
    787882                        }
     
    789884
    790885                // reset for next parameter
    791                 results.swap( nextResults );
    792                 nextResults.clear();
     886                genStart = genEnd;
    793887               
    794                 return ! results.empty();
    795         }       
     888                return genEnd != results.size();
     889        }
     890
     891        template<typename OutputIterator>
     892        void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result,
     893                        const std::vector<ArgPack>& results, OutputIterator out ) {
     894                ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
     895                // sum cost and accumulate actuals
     896                std::list<Expression*>& args = appExpr->get_args();
     897                Cost cost = Cost::zero;
     898                const ArgPack* pack = &result;
     899                while ( pack->expr ) {
     900                        args.push_front( pack->expr->clone() );
     901                        cost += pack->cost;
     902                        pack = &results[pack->parent];
     903                }
     904                // build and validate new alternative
     905                Alternative newAlt( appExpr, result.env, cost );
     906                PRINT(
     907                        std::cerr << "instantiate function success: " << appExpr << std::endl;
     908                        std::cerr << "need assertions:" << std::endl;
     909                        printAssertionSet( result.need, std::cerr, 8 );
     910                )
     911                inferParameters( result.need, result.have, newAlt, result.openVars, out );
     912        }
    796913
    797914        template<typename OutputIterator>
     
    818935
    819936                // iteratively build matches, one parameter at a time
    820                 std::vector<ArgPack> results{ ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } };
    821                 std::vector<ArgPack> nextResults{};
     937                std::vector<ArgPack> results;
     938                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
     939                std::size_t genStart = 0;
     940
    822941                for ( DeclarationWithType* formal : funcType->get_parameters() ) {
    823942                        ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
    824943                        if ( ! instantiateArgument(
    825                                         obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) )
     944                                        obj->get_type(), obj->get_init(), args, results, genStart, indexer ) )
    826945                                return;
    827946                }
    828947
    829                 // filter out results that don't use all the arguments, and aren't variadic
    830                 std::vector<ArgPack> finalResults{};
    831948                if ( funcType->get_isVarArgs() ) {
    832                         for ( ArgPack& result : results ) {
    833                                 // use rest of exploded tuple if present
    834                                 while ( result.nextExpl < result.expls.size() ) {
    835                                         const Alternative& actual = result.expls[result.nextExpl];
    836                                         result.env.addActual( actual.env, result.openVars );
    837                                         result.withArg( actual.expr );
    838                                         ++result.nextExpl;
    839                                 }
    840                         }
    841 
    842                         while ( ! results.empty() ) {
    843                                 // build combinations for all remaining arguments
    844                                 for ( ArgPack& result : results ) {
    845                                         // keep if used all arguments
    846                                         if ( result.nextArg >= args.size() ) {
    847                                                 finalResults.push_back( std::move(result) );
     949                        // append any unused arguments to vararg pack
     950                        std::size_t genEnd;
     951                        do {
     952                                genEnd = results.size();
     953
     954                                // iterate results
     955                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     956                                        // use remainder of exploded tuple if present
     957                                        if ( ! results[i].expls.empty() ) {
     958                                                const Alternative& actual = results[i].expls.front();
     959                                               
     960                                                TypeEnvironment env = results[i].env;
     961                                                OpenVarSet openVars = results[i].openVars;
     962
     963                                                env.addActual( actual.env, openVars );
     964
     965                                                std::vector<Alternative> newExpls(
     966                                                        std::next( results[i].expls.begin() ), results[i].expls.end() );
     967                                                results.emplace_back(
     968                                                        i, actual.expr, move(env), copy(results[i].need),
     969                                                        copy(results[i].have), move(openVars), results[i].nextArg, 0,
     970                                                        Cost::zero, move(newExpls) );
     971                                               
    848972                                                continue;
    849973                                        }
    850974
     975                                        // finish result when out of arguments
     976                                        if ( results[i].nextArg >= args.size() ) {
     977                                                validateFunctionAlternative( func, results[i], results, out );
     978
     979                                                continue;
     980                                        }
     981
    851982                                        // add each possible next argument
    852                                         for ( const Alternative& actual : args[result.nextArg] ) {
    853                                                 ArgPack aResult = result; // copy to clone everything
    854                                                 // add details of actual to result
    855                                                 aResult.env.addActual( actual.env, aResult.openVars );
    856                                                 Cost cost = actual.cost;
     983                                        auto j = results[i].nextArg;
     984                                        for ( const Alternative& actual : args[j] ) {
     985                                                // fresh copies of parent parameters for this iteration
     986                                                TypeEnvironment env = results[i].env;
     987                                                OpenVarSet openVars = results[i].openVars;
     988
     989                                                env.addActual( actual.env, openVars );
    857990
    858991                                                // explode argument
    859992                                                std::vector<Alternative> exploded;
    860993                                                Tuples::explode( actual, indexer, back_inserter( exploded ) );
    861 
    862                                                 // add exploded argument to arg list
    863                                                 for ( Alternative& aActual : exploded ) {
    864                                                         aResult.withArg( aActual.expr, cost );
    865                                                         cost = Cost::zero;
     994                                                if ( exploded.empty() ) {
     995                                                        // skip empty tuple arguments by (near-)cloning parent into next gen
     996                                                        results.emplace_back(
     997                                                                results[i].parent, results[i].expr.get(), move(env),
     998                                                                copy(results[i].need), copy(results[i].have), move(openVars),
     999                                                                j + 1, results[i].tupleStart, actual.cost + results[i].cost );
     1000                                                        continue;
    8661001                                                }
    867                                                 ++aResult.nextArg;
    868                                                 nextResults.push_back( std::move(aResult) );
     1002
     1003                                                // trim first element from exploded
     1004                                                std::vector<Alternative> newExpls;
     1005                                                newExpls.reserve( exploded.size() - 1 );
     1006                                                for ( std::size_t i = 1; i < exploded.size(); ++i ) {
     1007                                                        newExpls.push_back( move(exploded[i]) );
     1008                                                }
     1009                                                // add new result
     1010                                                results.emplace_back(
     1011                                                        i, actual.expr, move(env), copy(results[i].need),
     1012                                                        copy(results[i].have), move(openVars), j + 1, 0,
     1013                                                        actual.cost, move(newExpls) );
    8691014                                        }
    8701015                                }
    8711016
    872                                 // reset for next round
    873                                 results.swap( nextResults );
    874                                 nextResults.clear();
    875                         }
     1017                                genStart = genEnd;
     1018                        } while ( genEnd != results.size() );
    8761019                } else {
    8771020                        // filter out results that don't use all the arguments
    878                         for ( ArgPack& result : results ) {
    879                                 if ( result.nextExpl >= result.expls.size() && result.nextArg >= args.size() ) {
    880                                         finalResults.push_back( std::move(result) );
     1021                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
     1022                                ArgPack& result = results[i];
     1023                                if ( result.expls.empty() && result.nextArg >= args.size() ) {
     1024                                        validateFunctionAlternative( func, result, results, out );
    8811025                                }
    8821026                        }
    883                 }
    884 
    885                 // validate matching combos, add to final result list
    886                 for ( ArgPack& result : finalResults ) {
    887                         ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
    888                         Alternative newAlt( appExpr, result.env, sumCost( result.actuals ) );
    889                         makeExprList( result.actuals, appExpr->get_args() );
    890                         PRINT(
    891                                 std::cerr << "instantiate function success: " << appExpr << std::endl;
    892                                 std::cerr << "need assertions:" << std::endl;
    893                                 printAssertionSet( result.need, std::cerr, 8 );
    894                         )
    895                         inferParameters( result.need, result.have, newAlt, result.openVars, out );
    8961027                }
    8971028        }
     
    9561087                if ( ! funcOpFinder.alternatives.empty() ) {
    9571088                        // add function alternatives to front of argument list
    958                         argAlternatives.insert( argAlternatives.begin(), std::move(funcFinder) );
     1089                        argAlternatives.insert( argAlternatives.begin(), move(funcFinder) );
    9591090
    9601091                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
  • src/ResolvExpr/AlternativeFinder.h

    r6d2386e r403b388  
    3131
    3232namespace ResolvExpr {
     33        class ArgPack;
     34       
    3335        class AlternativeFinder : public Visitor {
    3436          public:
     
    126128                /// Adds alternatives for offsetof expressions, given the base type and name of the member
    127129                template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name );
     130                /// Takes a final result and checks if its assertions can be satisfied
     131                template<typename OutputIterator>
     132                void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out );
     133                /// Finds matching alternatives for a function, given a set of arguments
    128134                template<typename OutputIterator>
    129135                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const std::vector< AlternativeFinder >& args, OutputIterator out );
     136                /// Checks if assertion parameters match for a new alternative
    130137                template< typename OutputIterator >
    131138                void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );
Note: See TracChangeset for help on using the changeset viewer.