Changeset 9d5089e


Ignore:
Timestamp:
Jun 17, 2019, 7:14:58 PM (2 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
arm-eh, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
ea05f8d
Parents:
aba20d2
Message:

Port CandidateFinder::makeFunctionCandidates() and deps

Location:
src
Files:
9 edited

Legend:

Unmodified
Added
Removed
  • src/AST/TypeEnvironment.hpp

    raba20d2 r9d5089e  
    215215std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
    216216
    217 }
     217} // namespace ast
    218218
    219219// Local Variables: //
  • src/AST/porting.md

    raba20d2 r9d5089e  
    302302* `ExplodedActual.h` => `ExplodedArg.hpp`
    303303
     304`polyCost`
     305* switched order of `env`, `symtab` parameters for better consistency
     306
    304307[1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes
    305308
  • src/ResolvExpr/AlternativeFinder.cc

    raba20d2 r9d5089e  
    227227        }
    228228
    229         const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) {
    230                 if ( expr->result.as< ast::ReferenceType >() ) {
    231                         // cast away reference from expr
    232                         cost.incReference();
    233                         return new ast::CastExpr{ expr->location, expr, expr->result->stripReferences() };
    234                 }
    235                
    236                 return expr;
    237         }
    238 
    239229        template< typename InputIterator, typename OutputIterator >
    240230        void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
     
    518508        }
    519509
    520         /// Unique identifier for matching expression resolutions to their requesting expression
    521         UniqueId globalResnSlot = 0;
     510        /// Unique identifier for matching expression resolutions to their requesting expression (located in CandidateFinder.cpp)
     511        extern UniqueId globalResnSlot;
    522512
    523513        template< typename OutputIterator >
  • src/ResolvExpr/Candidate.hpp

    raba20d2 r9d5089e  
    5858
    5959        Candidate(
     60                const ast::Expr * x, const ast::TypeEnvironment & e, const ast::OpenVarSet & o,
     61                const ast::AssertionSet & n, const Cost & c, const Cost & cvt = Cost::zero )
     62        : expr( x ), cost( c ), cvtCost( cvt ), env( e ), open( o ), need( n.begin(), n.end() ) {}
     63
     64        Candidate(
    6065                const ast::Expr * x, ast::TypeEnvironment && e, ast::OpenVarSet && o,
    6166                ast::AssertionSet && n, const Cost & c, const Cost & cvt = Cost::zero )
  • src/ResolvExpr/CandidateFinder.cpp

    raba20d2 r9d5089e  
    2929#include "Resolver.h"
    3030#include "SatisfyAssertions.hpp"
    31 #include "typeops.h"              // for adjustExprType
     31#include "typeops.h"              // for adjustExprType, conversionCost, polyCost, specCost
    3232#include "Unify.h"
    3333#include "AST/Expr.hpp"
     
    4444namespace ResolvExpr {
    4545
     46using std::move;
     47
     48/// partner to move that copies any copyable type
     49template<typename T>
     50T copy( const T & x ) { return x; }
     51
     52const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) {
     53        if ( expr->result.as< ast::ReferenceType >() ) {
     54                // cast away reference from expr
     55                cost.incReference();
     56                return new ast::CastExpr{ expr->location, expr, expr->result->stripReferences() };
     57        }
     58       
     59        return expr;
     60}
     61
     62/// Unique identifier for matching expression resolutions to their requesting expression
     63UniqueId globalResnSlot = 0;
     64
    4665namespace {
    47 
    4866        /// First index is which argument, second is which alternative, third is which exploded element
    4967        using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >;
     
    6583        }
    6684
     85        /// Computes conversion cost between two types
     86        Cost computeConversionCost(
     87                const ast::Type * argType, const ast::Type * paramType, const ast::SymbolTable & symtab,
     88                const ast::TypeEnvironment & env
     89        ) {
     90                PRINT(
     91                        std::cerr << std::endl << "converting ";
     92                        ast::print( std::cerr, argType, 2 );
     93                        std::cerr << std::endl << " to ";
     94                        ast::print( std::cerr, paramType, 2 );
     95                        std::cerr << std::endl << "environment is: ";
     96                        ast::print( std::cerr, env, 2 );
     97                        std::cerr << std::endl;
     98                )
     99                Cost convCost = conversionCost( argType, paramType, symtab, env );
     100                PRINT(
     101                        std::cerr << std::endl << "cost is " << convCost << std::endl;
     102                )
     103                if ( convCost == Cost::infinity ) return convCost;
     104                convCost.incPoly( polyCost( paramType, symtab, env ) + polyCost( argType, symtab, env ) );
     105                PRINT(
     106                        std::cerr << "cost with polycost is " << convCost << std::endl;
     107                )
     108                return convCost;
     109        }
     110
     111        /// Computes conversion cost for a given expression to a given type
     112        const ast::Expr * computeExpressionConversionCost(
     113                const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost
     114        ) {
     115                Cost convCost = computeConversionCost( arg->result, paramType, symtab, env );
     116                outCost += convCost;
     117
     118                // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires
     119                // conversion. Ignore poly cost for now, since this requires resolution of the cast to
     120                // infer parameters and this does not currently work for the reason stated below
     121                Cost tmpCost = convCost;
     122                tmpCost.incPoly( -tmpCost.get_polyCost() );
     123                if ( tmpCost != Cost::zero ) {
     124                        ast::ptr< ast::Type > newType = paramType;
     125                        env.apply( newType );
     126                        return new ast::CastExpr{ arg->location, arg, newType };
     127
     128                        // xxx - *should* be able to resolve this cast, but at the moment pointers are not
     129                        // castable to zero_t, but are implicitly convertible. This is clearly inconsistent,
     130                        // once this is fixed it should be possible to resolve the cast.
     131                        // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable,
     132                        // but it shouldn't be because this makes the conversion from DT* to DT* since
     133                        // commontype(zero_t, DT*) is DT*, rather than nothing
     134
     135                        // CandidateFinder finder{ symtab, env };
     136                        // finder.find( arg, ResolvMode::withAdjustment() );
     137                        // assertf( finder.candidates.size() > 0,
     138                        //      "Somehow castable expression failed to find alternatives." );
     139                        // assertf( finder.candidates.size() == 1,
     140                        //      "Somehow got multiple alternatives for known cast expression." );
     141                        // return finder.candidates.front()->expr;
     142                }
     143
     144                return arg;
     145        }
     146
    67147        /// Computes conversion cost for a given candidate
    68148        Cost computeApplicationConversionCost(
    69                 const CandidateRef & cand, const ast::SymbolTable & symtab
     149                CandidateRef cand, const ast::SymbolTable & symtab
    70150        ) {
    71                 #warning unimplemented
    72                 (void)cand; (void)symtab;
    73                 assert(false);
    74                 return Cost::infinity;
     151                auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >();
     152                auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
     153                auto function = pointer->base.strict_as< ast::FunctionType >();
     154
     155                Cost convCost = Cost::zero;
     156                const auto & params = function->params;
     157                auto param = params.begin();
     158                auto & args = appExpr->args;
     159
     160                for ( unsigned i = 0; i < args.size(); ++i ) {
     161                        const ast::Type * argType = args[i]->result;
     162                        PRINT(
     163                                std::cerr << "arg expression:" << std::endl;
     164                                ast::print( std::cerr, args[i], 2 );
     165                                std::cerr << "--- results are" << std::endl;
     166                                ast::print( std::cerr, argType, 2 );
     167                        )
     168
     169                        if ( param == params.end() ) {
     170                                if ( function->isVarArgs ) {
     171                                        convCost.incUnsafe();
     172                                        PRINT( std::cerr << "end of params with varargs function: inc unsafe: "
     173                                                << convCost << std::endl; ; )
     174                                        // convert reference-typed expressions into value-typed expressions
     175                                        cand->expr = ast::mutate_field_index(
     176                                                appExpr, &ast::ApplicationExpr::args, i,
     177                                                referenceToRvalueConversion( args[i], convCost ) );
     178                                        continue;
     179                                } else return Cost::infinity;
     180                        }
     181
     182                        if ( auto def = args[i].as< ast::DefaultArgExpr >() ) {
     183                                // Default arguments should be free - don't include conversion cost.
     184                                // Unwrap them here because they are not relevant to the rest of the system
     185                                cand->expr = ast::mutate_field_index(
     186                                        appExpr, &ast::ApplicationExpr::args, i, def->expr );
     187                                ++param;
     188                                continue;
     189                        }
     190
     191                        // mark conversion cost and also specialization cost of param type
     192                        const ast::Type * paramType = (*param)->get_type();
     193                        cand->expr = ast::mutate_field_index(
     194                                appExpr, &ast::ApplicationExpr::args, i,
     195                                computeExpressionConversionCost(
     196                                        args[i], paramType, symtab, cand->env, convCost ) );
     197                        convCost.decSpec( specCost( paramType ) );
     198                        ++param;  // can't be in for-loop update because of the continue
     199                }
     200
     201                if ( param != params.end() ) return Cost::infinity;
     202
     203                // specialization cost of return types can't be accounted for directly, it disables
     204                // otherwise-identical calls, like this example based on auto-newline in the I/O lib:
     205                //
     206                //   forall(otype OS) {
     207                //     void ?|?(OS&, int);  // with newline
     208                //     OS&  ?|?(OS&, int);  // no newline, always chosen due to more specialization
     209                //   }
     210
     211                // mark type variable and specialization cost of forall clause
     212                convCost.incVar( function->forall.size() );
     213                for ( const ast::TypeDecl * td : function->forall ) {
     214                        convCost.decSpec( td->assertions.size() );
     215                }
     216
     217                return convCost;
     218        }
     219
     220        void makeUnifiableVars(
     221                const ast::ParameterizedType * type, ast::OpenVarSet & unifiableVars,
     222                ast::AssertionSet & need
     223        ) {
     224                for ( const ast::TypeDecl * tyvar : type->forall ) {
     225                        unifiableVars[ tyvar->name ] = ast::TypeDecl::Data{ tyvar };
     226                        for ( const ast::DeclWithType * assn : tyvar->assertions ) {
     227                                need[ assn ].isUsed = true;
     228                        }
     229                }
     230        }
     231
     232        /// Gets a default value from an initializer, nullptr if not present
     233        const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) {
     234                if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) {
     235                        if ( auto ce = si->value.as< ast::CastExpr >() ) {
     236                                return ce->arg.as< ast::ConstantExpr >();
     237                        } else {
     238                                return si->value.as< ast::ConstantExpr >();
     239                        }
     240                }
     241                return nullptr;
     242        }
     243
     244        /// State to iteratively build a match of parameter expressions to arguments
     245        struct ArgPack {
     246                std::size_t parent;          ///< Index of parent pack
     247                ast::ptr< ast::Expr > expr;  ///< The argument stored here
     248                Cost cost;                   ///< The cost of this argument
     249                ast::TypeEnvironment env;    ///< Environment for this pack
     250                ast::AssertionSet need;      ///< Assertions outstanding for this pack
     251                ast::AssertionSet have;      ///< Assertions found for this pack
     252                ast::OpenVarSet open;        ///< Open variables for this pack
     253                unsigned nextArg;            ///< Index of next argument in arguments list
     254                unsigned tupleStart;         ///< Number of tuples that start at this index
     255                unsigned nextExpl;           ///< Index of next exploded element
     256                unsigned explAlt;            ///< Index of alternative for nextExpl > 0
     257
     258                ArgPack()
     259                : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ),
     260                  tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
     261               
     262                ArgPack(
     263                        const ast::TypeEnvironment & env, const ast::AssertionSet & need,
     264                        const ast::AssertionSet & have, const ast::OpenVarSet & open )
     265                : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ),
     266                  open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
     267               
     268                ArgPack(
     269                        std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env,
     270                        ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open,
     271                        unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero,
     272                        unsigned nextExpl = 0, unsigned explAlt = 0 )
     273                : parent(parent), expr( expr ), cost( cost ), env( move( env ) ), need( move( need ) ),
     274                  have( move( have ) ), open( move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ),
     275                  nextExpl( nextExpl ), explAlt( explAlt ) {}
     276               
     277                ArgPack(
     278                        const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need,
     279                        ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added )
     280                : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( move( env ) ),
     281                  need( move( need ) ), have( move( have ) ), open( move( open ) ), nextArg( nextArg ),
     282                  tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {}
     283               
     284                /// true if this pack is in the middle of an exploded argument
     285                bool hasExpl() const { return nextExpl > 0; }
     286
     287                /// Gets the list of exploded candidates for this pack
     288                const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const {
     289                        return args[ nextArg-1 ][ explAlt ];
     290                }
     291               
     292                /// Ends a tuple expression, consolidating the appropriate args
     293                void endTuple( const std::vector< ArgPack > & packs ) {
     294                        // add all expressions in tuple to list, summing cost
     295                        std::deque< const ast::Expr * > exprs;
     296                        const ArgPack * pack = this;
     297                        if ( expr ) { exprs.emplace_front( expr ); }
     298                        while ( pack->tupleStart == 0 ) {
     299                                pack = &packs[pack->parent];
     300                                exprs.emplace_front( pack->expr );
     301                                cost += pack->cost;
     302                        }
     303                        // reset pack to appropriate tuple
     304                        std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() );
     305                        expr = new ast::TupleExpr{ expr->location, move( exprv ) };
     306                        tupleStart = pack->tupleStart - 1;
     307                        parent = pack->parent;
     308                }
     309        };
     310
     311        /// Instantiates an argument to match a parameter, returns false if no matching results left
     312        bool instantiateArgument(
     313                const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args,
     314                std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab,
     315                unsigned nTuples = 0
     316        ) {
     317                if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) {
     318                        // paramType is a TupleType -- group args into a TupleExpr
     319                        ++nTuples;
     320                        for ( const ast::Type * type : *tupleType ) {
     321                                // xxx - dropping initializer changes behaviour from previous, but seems correct
     322                                // ^^^ need to handle the case where a tuple has a default argument
     323                                if ( ! instantiateArgument(
     324                                        type, nullptr, args, results, genStart, symtab, nTuples ) ) return false;
     325                                nTuples = 0;
     326                        }
     327                        // re-constitute tuples for final generation
     328                        for ( auto i = genStart; i < results.size(); ++i ) {
     329                                results[i].endTuple( results );
     330                        }
     331                        return true;
     332                } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) {
     333                        // paramType is a ttype, consumes all remaining arguments
     334                       
     335                        // completed tuples; will be spliced to end of results to finish
     336                        std::vector< ArgPack > finalResults{};
     337
     338                        // iterate until all results completed
     339                        std::size_t genEnd;
     340                        ++nTuples;
     341                        do {
     342                                genEnd = results.size();
     343
     344                                // add another argument to results
     345                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     346                                        unsigned nextArg = results[i].nextArg;
     347                                       
     348                                        // use next element of exploded tuple if present
     349                                        if ( results[i].hasExpl() ) {
     350                                                const ExplodedArg & expl = results[i].getExpl( args );
     351
     352                                                unsigned nextExpl = results[i].nextExpl + 1;
     353                                                if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
     354
     355                                                results.emplace_back(
     356                                                        i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
     357                                                        copy( results[i].need ), copy( results[i].have ),
     358                                                        copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl,
     359                                                        results[i].explAlt );
     360
     361                                                continue;
     362                                        }
     363
     364                                        // finish result when out of arguments
     365                                        if ( nextArg >= args.size() ) {
     366                                                ArgPack newResult{
     367                                                        results[i].env, results[i].need, results[i].have, results[i].open };
     368                                                newResult.nextArg = nextArg;
     369                                                const ast::Type * argType = nullptr;
     370
     371                                                if ( nTuples > 0 || ! results[i].expr ) {
     372                                                        // first iteration or no expression to clone,
     373                                                        // push empty tuple expression
     374                                                        newResult.parent = i;
     375                                                        std::vector< ast::ptr< ast::Expr > > emptyList;
     376                                                        newResult.expr =
     377                                                                new ast::TupleExpr{ CodeLocation{}, move( emptyList ) };
     378                                                        argType = newResult.expr->result;
     379                                                } else {
     380                                                        // clone result to collect tuple
     381                                                        newResult.parent = results[i].parent;
     382                                                        newResult.cost = results[i].cost;
     383                                                        newResult.tupleStart = results[i].tupleStart;
     384                                                        newResult.expr = results[i].expr;
     385                                                        argType = newResult.expr->result;
     386
     387                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
     388                                                                // the case where a ttype value is passed directly is special,
     389                                                                // e.g. for argument forwarding purposes
     390                                                                // xxx - what if passing multiple arguments, last of which is
     391                                                                //       ttype?
     392                                                                // xxx - what would happen if unify was changed so that unifying
     393                                                                //       tuple
     394                                                                // types flattened both before unifying lists? then pass in
     395                                                                // TupleType (ttype) below.
     396                                                                --newResult.tupleStart;
     397                                                        } else {
     398                                                                // collapse leftover arguments into tuple
     399                                                                newResult.endTuple( results );
     400                                                                argType = newResult.expr->result;
     401                                                        }
     402                                                }
     403
     404                                                // check unification for ttype before adding to final
     405                                                if (
     406                                                        unify(
     407                                                                ttype, argType, newResult.env, newResult.need, newResult.have,
     408                                                                newResult.open, symtab )
     409                                                ) {
     410                                                        finalResults.emplace_back( move( newResult ) );
     411                                                }
     412
     413                                                continue;
     414                                        }
     415
     416                                        // add each possible next argument
     417                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     418                                                const ExplodedArg & expl = args[nextArg][j];
     419
     420                                                // fresh copies of parent parameters for this iteration
     421                                                ast::TypeEnvironment env = results[i].env;
     422                                                ast::OpenVarSet open = results[i].open;
     423
     424                                                env.addActual( expl.env, open );
     425
     426                                                // skip empty tuple arguments by (nearly) cloning parent into next gen
     427                                                if ( expl.exprs.empty() ) {
     428                                                        results.emplace_back(
     429                                                                results[i], move( env ), copy( results[i].need ),
     430                                                                copy( results[i].have ), move( open ), nextArg + 1, expl.cost );
     431                                                       
     432                                                        continue;
     433                                                }
     434
     435                                                // add new result
     436                                                results.emplace_back(
     437                                                        i, expl.exprs.front(), move( env ), copy( results[i].need ),
     438                                                        copy( results[i].have ), move( open ), nextArg + 1, nTuples,
     439                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
     440                                        }
     441                                }
     442
     443                                // reset for next round
     444                                genStart = genEnd;
     445                                nTuples = 0;
     446                        } while ( genEnd != results.size() );
     447
     448                        // splice final results onto results
     449                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
     450                                results.emplace_back( move( finalResults[i] ) );
     451                        }
     452                        return ! finalResults.empty();
     453                }
     454
     455                // iterate each current subresult
     456                std::size_t genEnd = results.size();
     457                for ( std::size_t i = genStart; i < genEnd; ++i ) {
     458                        unsigned nextArg = results[i].nextArg;
     459
     460                        // use remainder of exploded tuple if present
     461                        if ( results[i].hasExpl() ) {
     462                                const ExplodedArg & expl = results[i].getExpl( args );
     463                                const ast::Expr * expr = expl.exprs[ results[i].nextExpl ];
     464
     465                                ast::TypeEnvironment env = results[i].env;
     466                                ast::AssertionSet need = results[i].need, have = results[i].have;
     467                                ast::OpenVarSet open = results[i].open;
     468
     469                                const ast::Type * argType = expr->result;
     470
     471                                PRINT(
     472                                        std::cerr << "param type is ";
     473                                        ast::print( std::cerr, paramType );
     474                                        std::cerr << std::endl << "arg type is ";
     475                                        ast::print( std::cerr, argType );
     476                                        std::cerr << std::endl;
     477                                )
     478
     479                                if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
     480                                        unsigned nextExpl = results[i].nextExpl + 1;
     481                                        if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
     482
     483                                        results.emplace_back(
     484                                                i, expr, move( env ), move( need ), move( have ), move( open ), nextArg,
     485                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
     486                                }
     487
     488                                continue;
     489                        }
     490
     491                        // use default initializers if out of arguments
     492                        if ( nextArg >= args.size() ) {
     493                                if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) {
     494                                        ast::TypeEnvironment env = results[i].env;
     495                                        ast::AssertionSet need = results[i].need, have = results[i].have;
     496                                        ast::OpenVarSet open = results[i].open;
     497
     498                                        if ( unify( paramType, cnst->result, env, need, have, open, symtab ) ) {
     499                                                results.emplace_back(
     500                                                        i, new ast::DefaultArgExpr{ cnst->location, cnst }, move( env ),
     501                                                        move( need ), move( have ), move( open ), nextArg, nTuples );
     502                                        }
     503                                }
     504
     505                                continue;
     506                        }
     507
     508                        // Check each possible next argument
     509                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     510                                const ExplodedArg & expl = args[nextArg][j];
     511
     512                                // fresh copies of parent parameters for this iteration
     513                                ast::TypeEnvironment env = results[i].env;
     514                                ast::AssertionSet need = results[i].need, have = results[i].have;
     515                                ast::OpenVarSet open = results[i].open;
     516
     517                                env.addActual( expl.env, open );
     518
     519                                // skip empty tuple arguments by (nearly) cloning parent into next gen
     520                                if ( expl.exprs.empty() ) {
     521                                        results.emplace_back(
     522                                                results[i], move( env ), move( need ), move( have ), move( open ),
     523                                                nextArg + 1, expl.cost );
     524                                       
     525                                        continue;
     526                                }
     527
     528                                // consider only first exploded arg
     529                                const ast::Expr * expr = expl.exprs.front();
     530                                const ast::Type * argType = expr->result;
     531
     532                                PRINT(
     533                                        std::cerr << "param type is ";
     534                                        ast::print( std::cerr, paramType );
     535                                        std::cerr << std::endl << "arg type is ";
     536                                        ast::print( std::cerr, argType );
     537                                        std::cerr << std::endl;
     538                                )
     539
     540                                // attempt to unify types
     541                                if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
     542                                        // add new result
     543                                        results.emplace_back(
     544                                                i, expr, move( env ), move( need ), move( have ), move( open ),
     545                                                nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
     546                                }
     547                        }
     548                }
     549
     550                // reset for next parameter
     551                genStart = genEnd;
     552
     553                return genEnd != results.size();
    75554        }
    76555
     
    99578                }
    100579
     580                /// Set up candidate assertions for inference
     581                void inferParameters( CandidateRef & newCand, CandidateList & out ) {
     582                        // Set need bindings for any unbound assertions
     583                        UniqueId crntResnSlot = 0; // matching ID for this expression's assertions
     584                        for ( auto & assn : newCand->need ) {
     585                                // skip already-matched assertions
     586                                if ( assn.second.resnSlot != 0 ) continue;
     587                                // assign slot for expression if needed
     588                                if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
     589                                // fix slot to assertion
     590                                assn.second.resnSlot = crntResnSlot;
     591                        }
     592                        // pair slot to expression
     593                        if ( crntResnSlot != 0 ) {
     594                                newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot );
     595                        }
     596
     597                        // add to output list; assertion satisfaction will occur later
     598                        out.emplace_back( newCand );
     599                }
     600
     601                /// Completes a function candidate with arguments located
     602                void validateFunctionCandidate(
     603                        const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,
     604                        CandidateList & out
     605                ) {
     606                        ast::ApplicationExpr * appExpr =
     607                                new ast::ApplicationExpr{ func->expr->location, func->expr };
     608                        // sum cost and accumulate arguments
     609                        std::deque< const ast::Expr * > args;
     610                        Cost cost = func->cost;
     611                        const ArgPack * pack = &result;
     612                        while ( pack->expr ) {
     613                                args.emplace_front( pack->expr );
     614                                cost += pack->cost;
     615                                pack = &results[pack->parent];
     616                        }
     617                        std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() );
     618                        appExpr->args = move( vargs );
     619                        // build and validate new candidate
     620                        auto newCand =
     621                                std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost );
     622                        PRINT(
     623                                std::cerr << "instantiate function success: " << appExpr << std::endl;
     624                                std::cerr << "need assertions:" << std::endl;
     625                                ast::print( std::cerr, result.need, 2 );
     626                        )
     627                        inferParameters( newCand, out );
     628                }
     629
    101630                /// Builds a list of candidates for a function, storing them in out
    102631                void makeFunctionCandidates(
     
    104633                        const ExplodedArgs_new & args, CandidateList & out
    105634                ) {
    106                         #warning unimplemented
    107                         (void)func; (void)funcType; (void)args; (void)out;
    108                         assert(false);
     635                        ast::OpenVarSet funcOpen;
     636                        ast::AssertionSet funcNeed, funcHave;
     637                        ast::TypeEnvironment funcEnv{ func->env };
     638                        makeUnifiableVars( funcType, funcOpen, funcNeed );
     639                        // add all type variables as open variables now so that those not used in the parameter
     640                        // list are still considered open
     641                        funcEnv.add( funcType->forall );
     642
     643                        if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) {
     644                                // attempt to narrow based on expected target type
     645                                const ast::Type * returnType = funcType->returns.front()->get_type();
     646                                if ( ! unify(
     647                                        returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab )
     648                                ) {
     649                                        // unification failed, do not pursue this candidate
     650                                        return;
     651                                }
     652                        }
     653
     654                        // iteratively build matches, one parameter at a time
     655                        std::vector< ArgPack > results;
     656                        results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen );
     657                        std::size_t genStart = 0;
     658
     659                        for ( const ast::DeclWithType * param : funcType->params ) {
     660                                auto obj = strict_dynamic_cast< const ast::ObjectDecl * >( param );
     661                                // Try adding the arguments corresponding to the current parameter to the existing
     662                                // matches
     663                                if ( ! instantiateArgument(
     664                                        obj->type, obj->init, args, results, genStart, symtab ) ) return;
     665                        }
     666
     667                        if ( funcType->isVarArgs ) {
     668                                // append any unused arguments to vararg pack
     669                                std::size_t genEnd;
     670                                do {
     671                                        genEnd = results.size();
     672
     673                                        // iterate results
     674                                        for ( std::size_t i = genStart; i < genEnd; ++i ) {
     675                                                unsigned nextArg = results[i].nextArg;
     676
     677                                                // use remainder of exploded tuple if present
     678                                                if ( results[i].hasExpl() ) {
     679                                                        const ExplodedArg & expl = results[i].getExpl( args );
     680
     681                                                        unsigned nextExpl = results[i].nextExpl + 1;
     682                                                        if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
     683
     684                                                        results.emplace_back(
     685                                                                i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
     686                                                                copy( results[i].need ), copy( results[i].have ),
     687                                                                copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl,
     688                                                                results[i].explAlt );
     689
     690                                                        continue;
     691                                                }
     692
     693                                                // finish result when out of arguments
     694                                                if ( nextArg >= args.size() ) {
     695                                                        validateFunctionCandidate( func, results[i], results, out );
     696
     697                                                        continue;
     698                                                }
     699
     700                                                // add each possible next argument
     701                                                for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
     702                                                        const ExplodedArg & expl = args[nextArg][j];
     703
     704                                                        // fresh copies of parent parameters for this iteration
     705                                                        ast::TypeEnvironment env = results[i].env;
     706                                                        ast::OpenVarSet open = results[i].open;
     707
     708                                                        env.addActual( expl.env, open );
     709
     710                                                        // skip empty tuple arguments by (nearly) cloning parent into next gen
     711                                                        if ( expl.exprs.empty() ) {
     712                                                                results.emplace_back(
     713                                                                        results[i], move( env ), copy( results[i].need ),
     714                                                                        copy( results[i].have ), move( open ), nextArg + 1,
     715                                                                        expl.cost );
     716
     717                                                                continue;
     718                                                        }
     719
     720                                                        // add new result
     721                                                        results.emplace_back(
     722                                                                i, expl.exprs.front(), move( env ), copy( results[i].need ),
     723                                                                copy( results[i].have ), move( open ), nextArg + 1, 0, expl.cost,
     724                                                                expl.exprs.size() == 1 ? 0 : 1, j );
     725                                                }
     726                                        }
     727
     728                                        genStart = genEnd;
     729                                } while( genEnd != results.size() );
     730                        } else {
     731                                // filter out the results that don't use all the arguments
     732                                for ( std::size_t i = genStart; i < results.size(); ++i ) {
     733                                        ArgPack & result = results[i];
     734                                        if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
     735                                                validateFunctionCandidate( func, result, results, out );
     736                                        }
     737                                }
     738                        }
    109739                }
    110740
     
    189819                                        funcE.emplace_back( *func, symtab );
    190820                                }
    191                                 argExpansions.emplace_front( std::move( funcE ) );
     821                                argExpansions.emplace_front( move( funcE ) );
    192822
    193823                                for ( const CandidateRef & op : opFinder ) {
     
    233863                                if ( cvtCost != Cost::infinity ) {
    234864                                        withFunc->cvtCost = cvtCost;
    235                                         candidates.emplace_back( std::move( withFunc ) );
    236                                 }
    237                         }
    238                         found = std::move( candidates );
     865                                        candidates.emplace_back( move( withFunc ) );
     866                                }
     867                        }
     868                        found = move( candidates );
    239869
    240870                        // use a new list so that candidates are not examined by addAnonConversions twice
     
    3761006                                                new ast::LogicalExpr{
    3771007                                                        logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
    378                                                 std::move( env ), std::move( open ), std::move( need ),
    379                                                 r1->cost + r2->cost );
     1008                                                move( env ), move( open ), move( need ), r1->cost + r2->cost );
    3801009                                }
    3811010                        }
     
    5121141
    5131142                                addCandidate(
    514                                         new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },
    515                                         std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
     1143                                        new ast::TupleExpr{ tupleExpr->location, move( exprs ) },
     1144                                        move( env ), move( open ), move( need ), sumCost( subs ) );
    5161145                        }
    5171146                }
     
    6281257                        cand->env.applyFree( newResult );
    6291258                        cand->expr = ast::mutate_field(
    630                                 cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
     1259                                cand->expr.get(), &ast::Expr::result, move( newResult ) );
    6311260                       
    6321261                        out.emplace_back( cand );
     
    6661295
    6671296                // reset candidates
    668                 candidates = std::move( satisfied );
     1297                candidates = move( satisfied );
    6691298        }
    6701299
     
    6901319
    6911320                auto oldsize = candidates.size();
    692                 candidates = std::move( pruned );
     1321                candidates = move( pruned );
    6931322
    6941323                PRINT(
  • src/ResolvExpr/ConversionCost.cc

    raba20d2 r9d5089e  
    8585                        });
    8686                } else {
    87                         PassVisitor<ConversionCost> converter( dest, indexer, env, conversionCost );
     87                        PassVisitor<ConversionCost> converter(
     88                                dest, indexer, env,
     89                                (Cost (*)(Type*, Type*, const SymTab::Indexer&, const TypeEnvironment&))
     90                                        conversionCost );
    8891                        src->accept( converter );
    8992                        if ( converter.pass.get_cost() == Cost::infinity ) {
     
    134137                        } else {
    135138                                PRINT( std::cerr << "reference to rvalue conversion" << std::endl; )
    136                                 PassVisitor<ConversionCost> converter( dest, indexer, env, conversionCost );
     139                                PassVisitor<ConversionCost> converter(
     140                                        dest, indexer, env,
     141                                        (Cost (*)(Type*, Type*, const SymTab::Indexer&, const TypeEnvironment&))
     142                                                conversionCost );
    137143                                src->accept( converter );
    138144                                return converter.pass.get_cost();
     
    482488                } // if
    483489        }
     490
     491        Cost conversionCost(
     492                const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
     493                const ast::TypeEnvironment & env
     494        ) {
     495                #warning unimplemented
     496                (void)src; (void)dst; (void)symtab; (void)env;
     497                assert(false);
     498                return Cost::zero;
     499        }
    484500} // namespace ResolvExpr
    485501
  • src/ResolvExpr/PolyCost.cc

    raba20d2 r9d5089e  
    1414//
    1515
     16#include "AST/SymbolTable.hpp"
     17#include "AST/Type.hpp"
     18#include "AST/TypeEnvironment.hpp"
    1619#include "Common/PassVisitor.h"
    1720#include "SymTab/Indexer.h"   // for Indexer
     
    5457        }
    5558
     59        int polyCost(
     60                const ast::Type * type, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env
     61        ) {
     62                #warning unimplemented
     63                (void)type; (void)symtab; (void)env;
     64                assert(false);
     65                return 0;
     66        }
     67
    5668} // namespace ResolvExpr
    5769
  • src/ResolvExpr/SpecCost.cc

    raba20d2 r9d5089e  
    1717#include <list>
    1818
     19#include "AST/Type.hpp"
    1920#include "Common/PassVisitor.h"
    2021#include "SynTree/Declaration.h"
     
    111112                return counter.pass.get_count();
    112113        }
     114
     115        int specCost( const ast::Type * ty ) {
     116                #warning unimplmented
     117                (void)ty;
     118                assert(false);
     119                return 0;
     120        }
    113121} // namespace ResolvExpr
    114122
  • src/ResolvExpr/typeops.h

    raba20d2 r9d5089e  
    8181        // in ConversionCost.cc
    8282        Cost conversionCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env );
     83        Cost conversionCost(
     84                const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
     85                const ast::TypeEnvironment & env );
    8386
    8487        // in AlternativeFinder.cc
     
    127130        // in PolyCost.cc
    128131        int polyCost( Type *type, const TypeEnvironment &env, const SymTab::Indexer &indexer );
     132        int polyCost(
     133                const ast::Type * type, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env );
    129134
    130135        // in SpecCost.cc
    131136        int specCost( Type *type );
     137        int specCost( const ast::Type * type );
    132138
    133139        // in Occurs.cc
     
    146152        // in AlternativeFinder.cc
    147153        void referenceToRvalueConversion( Expression *& expr, Cost & cost );
     154        // in CandidateFinder.cpp
    148155        const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost );
    149156
Note: See TracChangeset for help on using the changeset viewer.