Changeset 178e4ec for src/ResolvExpr


Ignore:
Timestamp:
Nov 23, 2017, 5:12:22 PM (8 years ago)
Author:
Rob Schluntz <rschlunt@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
3787dc1
Parents:
8dceeb7 (diff), 62194cb (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' of plg.uwaterloo.ca:/u/cforall/software/cfa/cfa-cc

Location:
src/ResolvExpr
Files:
2 added
4 edited

Legend:

Unmodified
Added
Removed

  • src/ResolvExpr/Alternative.h

    r8dceeb7 r178e4ec  
    3737                void print( std::ostream &os, Indenter indent = {} ) const;
    3838
     39                /// Returns the stored expression, but released from management of this Alternative
     40                Expression* release_expr() {
     41                        Expression* tmp = expr;
     42                        expr = nullptr;
     43                        return tmp;
     44                }
     45
    3946                Cost cost;
    4047                Cost cvtCost;

  • src/ResolvExpr/AlternativeFinder.cc

    r8dceeb7 r178e4ec  
    3030#include "Common/utility.h"        // for deleteAll, printAll, CodeLocation
    3131#include "Cost.h"                  // for Cost, Cost::zero, operator<<, Cost...
     32#include "ExplodedActual.h"        // for ExplodedActual
    3233#include "InitTweak/InitTweak.h"   // for getFunctionName
    3334#include "RenameVars.h"            // for RenameVars, global_renamer
    … …  
    590591                unsigned nextArg;                  ///< Index of next argument in arguments list
    591592                unsigned tupleStart;               ///< Number of tuples that start at this index
    592                 // TODO fix this somehow
    593                 std::vector<Alternative> expls;    ///< Exploded actuals left over from last match
     593                unsigned nextExpl;                 ///< Index of next exploded element
     594                unsigned explAlt;                  ///< Index of alternative for nextExpl > 0
    594595
    595596                ArgPack()
    596597                        : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
    597                           tupleStart(0), expls() {}
     598
     599                          tupleStart(0), nextExpl(0), explAlt(0) {}
    598600
    599601                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
    600602                                const OpenVarSet& openVars)
    601603                        : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
    602                           openVars(openVars), nextArg(0), tupleStart(0), expls() {}
     604                          openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
    603605
    604606                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
    605607                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
    606                                 unsigned tupleStart = 0, Cost cost = Cost::zero,
    607                                 std::vector<Alternative>&& expls = std::vector<Alternative>{} )
     608                                unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
     609                                unsigned explAlt = 0 )
    608610                        : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
    609611                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
    610                           expls(move(expls)) {}
     612                          nextExpl(nextExpl), explAlt(explAlt) {}
    611613
    612614                ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
    … …  
    614616                        : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added),
    615617                          env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)),
    616                           nextArg(nextArg), tupleStart(o.tupleStart), expls() {}
    617 
    618 
    619                 // ArgPack(const ArgPack& o)
    620                 //      : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), env(o.env),
    621                 //        need(o.need), have(o.have), openVars(o.openVars), nextArg(o.nextArg),
    622                 //        tupleStart(o.tupleStart), expls(o.expls) {}
    623 
    624                 // ArgPack(ArgPack&&) = default;
     618                          nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
     619
     620                /// true iff this pack is in the middle of an exploded argument
     621                bool hasExpl() const { return nextExpl > 0; }
     622
     623                /// Gets the list of exploded alternatives for this pack
     624                const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
     625                        return args[nextArg-1][explAlt];
     626                }
    625627
    626628                /// Ends a tuple expression, consolidating the appropriate actuals
    … …  
    644646        /// Instantiates an argument to match a formal, returns false if no results left
    645647        bool instantiateArgument( Type* formalType, Initializer* initializer,
    646                         const std::vector< AlternativeFinder >& args, std::vector<ArgPack>& results,
    647                         std::size_t& genStart, const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
     648                        const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
     649                        const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
    648650                if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) {
    649651                        // formalType is a TupleType - group actuals into a TupleExpr
    … …  
    676678                                // add another argument to results
    677679                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
    678                                         // use remainder of exploded tuple if present
    679                                         if ( ! results[i].expls.empty() ) {
    680                                                 const Alternative& actual = results[i].expls.front();
    681 
    682                                                 TypeEnvironment env = results[i].env;
    683                                                 OpenVarSet openVars = results[i].openVars;
    684 
    685                                                 env.addActual( actual.env, openVars );
    686 
    687                                                 std::vector<Alternative> newExpls(
    688                                                         std::next( results[i].expls.begin() ), results[i].expls.end() );
     680                                        auto nextArg = results[i].nextArg;
     681
     682                                        // use next element of exploded tuple if present
     683                                        if ( results[i].hasExpl() ) {
     684                                                const ExplodedActual& expl = results[i].getExpl( args );
     685
     686                                                unsigned nextExpl = results[i].nextExpl + 1;
     687                                                if ( nextExpl == expl.exprs.size() ) {
     688                                                        nextExpl = 0;
     689                                                }
     690
    689691                                                results.emplace_back(
    690                                                         i, actual.expr, move(env), copy(results[i].need),
    691                                                         copy(results[i].have), move(openVars), results[i].nextArg, nTuples,
    692                                                         Cost::zero, move(newExpls) );
     692                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
     693                                                        copy(results[i].need), copy(results[i].have),
     694                                                        copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
     695                                                        results[i].explAlt );
    693696
    694697                                                continue;
    … …  
    696699
    697700                                        // finish result when out of arguments
    698                                         if ( results[i].nextArg >= args.size() ) {
     701                                        if ( nextArg >= args.size() ) {
    699702                                                ArgPack newResult{
    700703                                                        results[i].env, results[i].need, results[i].have,
    701704                                                        results[i].openVars };
    702                                                 newResult.nextArg = results[i].nextArg;
     705                                                newResult.nextArg = nextArg;
    703706                                                Type* argType;
    704707
    … …  
    744747
    745748                                        // add each possible next argument
    746                                         auto j = results[i].nextArg;
    747                                         for ( const Alternative& actual : args[j] ) {
     749                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     750                                                const ExplodedActual& expl = args[nextArg][j];
     751
    748752                                                // fresh copies of parent parameters for this iteration
    749753                                                TypeEnvironment env = results[i].env;
    750754                                                OpenVarSet openVars = results[i].openVars;
    751755
    752                                                 env.addActual( actual.env, openVars );
    753 
    754                                                 // explode argument
    755                                                 std::vector<Alternative> exploded;
    756                                                 Tuples::explode( actual, indexer, back_inserter( exploded ) );
    757                                                 if ( exploded.empty() ) {
    758                                                         // skip empty tuple arguments by (near-)cloning parent into next gen
     756                                                env.addActual( expl.env, openVars );
     757
     758                                                // skip empty tuple arguments by (near-)cloning parent into next gen
     759                                                if ( expl.exprs.empty() ) {
    759760                                                        results.emplace_back(
    760761                                                                results[i], move(env), copy(results[i].need),
    761                                                                 copy(results[i].have), move(openVars), j + 1, actual.cost );
     762                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
    762763
    763764                                                        continue;
    764765                                                }
    765766
    766                                                 // trim first element from exploded
    767                                                 std::vector<Alternative> newExpls;
    768                                                 newExpls.reserve( exploded.size() - 1 );
    769                                                 for ( std::size_t i = 1; i < exploded.size(); ++i ) {
    770                                                         newExpls.push_back( move(exploded[i]) );
    771                                                 }
    772767                                                // add new result
    773768                                                results.emplace_back(
    774                                                         i, exploded.front().expr, move(env), copy(results[i].need),
    775                                                         copy(results[i].have), move(openVars), results[i].nextArg + 1,
    776                                                         nTuples, actual.cost, move(newExpls) );
     769                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
     770                                                        copy(results[i].have), move(openVars), nextArg + 1,
     771                                                        nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
    777772                                        }
    778773                                }
    … …  
    793788                std::size_t genEnd = results.size();
    794789                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     790                        auto nextArg = results[i].nextArg;
     791
    795792                        // use remainder of exploded tuple if present
    796                         if ( ! results[i].expls.empty() ) {
    797                                 const Alternative& actual = results[i].expls.front();
     793                        if ( results[i].hasExpl() ) {
     794                                const ExplodedActual& expl = results[i].getExpl( args );
     795                                Expression* expr = expl.exprs[results[i].nextExpl].get();
    798796
    799797                                TypeEnvironment env = results[i].env;
    … …  
    801799                                OpenVarSet openVars = results[i].openVars;
    802800
    803                                 env.addActual( actual.env, openVars );
    804                                 Type* actualType = actual.expr->get_result();
     801                                Type* actualType = expr->get_result();
    805802
    806803                                PRINT(
    … …  
    813810
    814811                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
    815                                         std::vector<Alternative> newExpls(
    816                                                 std::next( results[i].expls.begin() ), results[i].expls.end() );
     812                                        unsigned nextExpl = results[i].nextExpl + 1;
     813                                        if ( nextExpl == expl.exprs.size() ) {
     814                                                nextExpl = 0;
     815                                        }
     816
    817817                                        results.emplace_back(
    818                                                 i, actual.expr, move(env), move(need), move(have), move(openVars),
    819                                                 results[i].nextArg, nTuples, Cost::zero, move(newExpls) );;
     818                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg,
     819                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
    820820                                }
    821821
    … …  
    824824
    825825                        // use default initializers if out of arguments
    826                         if ( results[i].nextArg >= args.size() ) {
     826                        if ( nextArg >= args.size() ) {
    827827                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
    828828                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
    … …  
    835835                                                        results.emplace_back(
    836836                                                                i, cnstExpr, move(env), move(need), move(have),
    837                                                                 move(openVars), results[i].nextArg, nTuples );
     837                                                                move(openVars), nextArg, nTuples );
    838838                                                }
    839839                                        }
    … …  
    844844
    845845                        // Check each possible next argument
    846                         auto j = results[i].nextArg;
    847                         for ( const Alternative& actual : args[j] ) {
     846                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     847                                const ExplodedActual& expl = args[nextArg][j];
     848
    848849                                // fresh copies of parent parameters for this iteration
    849850                                TypeEnvironment env = results[i].env;
    … …  
    851852                                OpenVarSet openVars = results[i].openVars;
    852853
    853                                 env.addActual( actual.env, openVars );
    854 
    855                                 // explode argument
    856                                 std::vector<Alternative> exploded;
    857                                 Tuples::explode( actual, indexer, back_inserter( exploded ) );
    858                                 if ( exploded.empty() ) {
    859                                         // skip empty tuple arguments by (near-)cloning parent into next gen
     854                                env.addActual( expl.env, openVars );
     855
     856                                // skip empty tuple arguments by (near-)cloning parent into next gen
     857                                if ( expl.exprs.empty() ) {
    860858                                        results.emplace_back(
    861                                                 results[i], move(env), move(need), move(have), move(openVars), j + 1,
    862                                                 actual.cost );
     859                                                results[i], move(env), move(need), move(have), move(openVars),
     860                                                nextArg + 1, expl.cost );
    863861
    864862                                        continue;
    … …  
    866864
    867865                                // consider only first exploded actual
    868                                 const Alternative& aActual = exploded.front();
    869                                 Type* actualType = aActual.expr->get_result()->clone();
     866                                Expression* expr = expl.exprs.front().get();
     867                                Type* actualType = expr->get_result()->clone();
    870868
    871869                                PRINT(
    … …  
    879877                                // attempt to unify types
    880878                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
    881                                         // trim first element from exploded
    882                                         std::vector<Alternative> newExpls;
    883                                         newExpls.reserve( exploded.size() - 1 );
    884                                         for ( std::size_t i = 1; i < exploded.size(); ++i ) {
    885                                                 newExpls.push_back( move(exploded[i]) );
    886                                         }
    887879                                        // add new result
    888880                                        results.emplace_back(
    889                                                 i, aActual.expr, move(env), move(need), move(have), move(openVars),
    890                                                 j + 1, nTuples, actual.cost, move(newExpls) );
     881                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
     882                                                nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
    891883                                }
    892884                        }
    … …  
    924916        template<typename OutputIterator>
    925917        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func,
    926                         FunctionType *funcType, const std::vector< AlternativeFinder > &args,
    927                         OutputIterator out ) {
     918                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
    928919                OpenVarSet funcOpenVars;
    929920                AssertionSet funcNeed, funcHave;
    … …  
    964955                                // iterate results
    965956                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     957                                        auto nextArg = results[i].nextArg;
     958
    966959                                        // use remainder of exploded tuple if present
    967                                         if ( ! results[i].expls.empty() ) {
    968                                                 const Alternative& actual = results[i].expls.front();
    969 
    970                                                 TypeEnvironment env = results[i].env;
    971                                                 OpenVarSet openVars = results[i].openVars;
    972 
    973                                                 env.addActual( actual.env, openVars );
    974 
    975                                                 std::vector<Alternative> newExpls(
    976                                                         std::next( results[i].expls.begin() ), results[i].expls.end() );
     960                                        if ( results[i].hasExpl() ) {
     961                                                const ExplodedActual& expl = results[i].getExpl( args );
     962
     963                                                unsigned nextExpl = results[i].nextExpl + 1;
     964                                                if ( nextExpl == expl.exprs.size() ) {
     965                                                        nextExpl = 0;
     966                                                }
     967
    977968                                                results.emplace_back(
    978                                                         i, actual.expr, move(env), copy(results[i].need),
    979                                                         copy(results[i].have), move(openVars), results[i].nextArg, 0,
    980                                                         Cost::zero, move(newExpls) );
     969                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
     970                                                        copy(results[i].need), copy(results[i].have),
     971                                                        copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
     972                                                        results[i].explAlt );
    981973
    982974                                                continue;
    … …  
    984976
    985977                                        // finish result when out of arguments
    986                                         if ( results[i].nextArg >= args.size() ) {
     978                                        if ( nextArg >= args.size() ) {
    987979                                                validateFunctionAlternative( func, results[i], results, out );
    988980
    … …  
    991983
    992984                                        // add each possible next argument
    993                                         auto j = results[i].nextArg;
    994                                         for ( const Alternative& actual : args[j] ) {
     985                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     986                                                const ExplodedActual& expl = args[nextArg][j];
     987
    995988                                                // fresh copies of parent parameters for this iteration
    996989                                                TypeEnvironment env = results[i].env;
    997990                                                OpenVarSet openVars = results[i].openVars;
    998991
    999                                                 env.addActual( actual.env, openVars );
    1000 
    1001                                                 // explode argument
    1002                                                 std::vector<Alternative> exploded;
    1003                                                 Tuples::explode( actual, indexer, back_inserter( exploded ) );
    1004                                                 if ( exploded.empty() ) {
    1005                                                         // skip empty tuple arguments by (near-)cloning parent into next gen
     992                                                env.addActual( expl.env, openVars );
     993
     994                                                // skip empty tuple arguments by (near-)cloning parent into next gen
     995                                                if ( expl.exprs.empty() ) {
    1006996                                                        results.emplace_back(
    1007997                                                                results[i], move(env), copy(results[i].need),
    1008                                                                 copy(results[i].have), move(openVars), j + 1, actual.cost );
     998                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
     999
    10091000                                                        continue;
    10101001                                                }
    10111002
    1012                                                 // trim first element from exploded
    1013                                                 std::vector<Alternative> newExpls;
    1014                                                 newExpls.reserve( exploded.size() - 1 );
    1015                                                 for ( std::size_t i = 1; i < exploded.size(); ++i ) {
    1016                                                         newExpls.push_back( move(exploded[i]) );
    1017                                                 }
    10181003                                                // add new result
    10191004                                                results.emplace_back(
    1020                                                         i, exploded.front().expr, move(env), copy(results[i].need),
    1021                                                         copy(results[i].have), move(openVars), j + 1, 0,
    1022                                                         actual.cost, move(newExpls) );
     1005                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
     1006                                                        copy(results[i].have), move(openVars), nextArg + 1, 0,
     1007                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
    10231008                                        }
    10241009                                }
    … …  
    10301015                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
    10311016                                ArgPack& result = results[i];
    1032                                 if ( result.expls.empty() && result.nextArg >= args.size() ) {
     1017                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
    10331018                                        validateFunctionAlternative( func, result, results, out );
    10341019                                }
    … …  
    10601045                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
    10611046                )
     1047
     1048                // pre-explode arguments
     1049                ExplodedArgs argExpansions;
     1050                argExpansions.reserve( argAlternatives.size() );
     1051
     1052                for ( const AlternativeFinder& arg : argAlternatives ) {
     1053                        argExpansions.emplace_back();
     1054                        auto& argE = argExpansions.back();
     1055                        argE.reserve( arg.alternatives.size() );
     1056
     1057                        for ( const Alternative& actual : arg ) {
     1058                                argE.emplace_back( actual, indexer );
     1059                        }
     1060                }
    10621061
    10631062                AltList candidates;
    … …  
    10741073                                                Alternative newFunc( *func );
    10751074                                                referenceToRvalueConversion( newFunc.expr );
    1076                                                 makeFunctionAlternatives( newFunc, function, argAlternatives,
     1075                                                makeFunctionAlternatives( newFunc, function, argExpansions,
    10771076                                                        std::back_inserter( candidates ) );
    10781077                                        }
    … …  
    10831082                                                        Alternative newFunc( *func );
    10841083                                                        referenceToRvalueConversion( newFunc.expr );
    1085                                                         makeFunctionAlternatives( newFunc, function, argAlternatives,
     1084                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
    10861085                                                                std::back_inserter( candidates ) );
    10871086                                                } // if
    … …  
    10951094                // try each function operator ?() with each function alternative
    10961095                if ( ! funcOpFinder.alternatives.empty() ) {
    1097                         // add function alternatives to front of argument list
    1098                         argAlternatives.insert( argAlternatives.begin(), move(funcFinder) );
     1096                        // add exploded function alternatives to front of argument list
     1097                        std::vector<ExplodedActual> funcE;
     1098                        funcE.reserve( funcFinder.alternatives.size() );
     1099                        for ( const Alternative& actual : funcFinder ) {
     1100                                funcE.emplace_back( actual, indexer );
     1101                        }
     1102                        argExpansions.insert( argExpansions.begin(), move(funcE) );
    10991103
    11001104                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
    … …  
    11081112                                                        Alternative newFunc( *funcOp );
    11091113                                                        referenceToRvalueConversion( newFunc.expr );
    1110                                                         makeFunctionAlternatives( newFunc, function, argAlternatives,
     1114                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
    11111115                                                                std::back_inserter( candidates ) );
    11121116                                                }

  • src/ResolvExpr/AlternativeFinder.h

    r8dceeb7 r178e4ec  
    2121
    2222#include "Alternative.h"                 // for AltList, Alternative
     23#include "ExplodedActual.h"              // for ExplodedActual
    2324#include "ResolvExpr/Cost.h"             // for Cost, Cost::infinity
    2425#include "ResolvExpr/TypeEnvironment.h"  // for AssertionSet, OpenVarSet
    … …  
    3233namespace ResolvExpr {
    3334        struct ArgPack;
     35
     36        /// First index is which argument, second index is which alternative for that argument,
     37        /// third index is which exploded element of that alternative
     38        using ExplodedArgs = std::vector< std::vector< ExplodedActual > >;
    3439
    3540        class AlternativeFinder : public Visitor {
    … …  
    133138                /// Finds matching alternatives for a function, given a set of arguments
    134139                template<typename OutputIterator>
    135                 void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const std::vector< AlternativeFinder >& args, OutputIterator out );
     140                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
    136141                /// Checks if assertion parameters match for a new alternative
    137142                template< typename OutputIterator >

  • src/ResolvExpr/module.mk

    r8dceeb7 r178e4ec  
    3232       ResolvExpr/Occurs.cc \
    3333       ResolvExpr/TypeEnvironment.cc \
    34        ResolvExpr/CurrentObject.cc
     34       ResolvExpr/CurrentObject.cc \
     35       ResolvExpr/ExplodedActual.cc
Note: See TracChangeset for help on using the changeset viewer.