Index: src/AST/Convert.cpp =================================================================== --- src/AST/Convert.cpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/AST/Convert.cpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -2343,5 +2343,6 @@ old->location, GET_ACCEPT_1(arg, Expr), - old->isGenerated ? ast::GeneratedCast : ast::ExplicitCast + old->isGenerated ? ast::GeneratedCast : ast::ExplicitCast, + (ast::CastExpr::CastKind) old->kind ) ); Index: src/AST/Expr.cpp =================================================================== --- src/AST/Expr.cpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/AST/Expr.cpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -186,6 +186,6 @@ // --- CastExpr -CastExpr::CastExpr( const CodeLocation & loc, const Expr * a, GeneratedFlag g ) -: Expr( loc, new VoidType{} ), arg( a ), isGenerated( g ) {} +CastExpr::CastExpr( const CodeLocation & loc, const Expr * a, GeneratedFlag g, CastKind kind ) +: Expr( loc, new VoidType{} ), arg( a ), isGenerated( g ), kind( kind ) {} bool CastExpr::get_lvalue() const { Index: src/AST/Expr.hpp =================================================================== --- src/AST/Expr.hpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/AST/Expr.hpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -55,4 +55,6 @@ const Expr * e ) : decl( id ), declptr( declptr ), actualType( actual ), formalType( formal ), expr( e ) {} + + operator bool() {return declptr;} }; @@ -335,8 +337,16 @@ GeneratedFlag isGenerated; + enum CastKind { + Default, // C + Coerce, // reinterpret cast + Return // overload selection + }; + + CastKind kind = Default; + CastExpr( const CodeLocation & loc, const Expr * a, const Type * to, - GeneratedFlag g = GeneratedCast ) : Expr( loc, to ), arg( a ), isGenerated( g ) {} + GeneratedFlag g = GeneratedCast, CastKind kind = Default ) : Expr( loc, to ), arg( a ), isGenerated( g ), kind( kind ) {} /// Cast-to-void - CastExpr( const CodeLocation & loc, const Expr * a, GeneratedFlag g = GeneratedCast ); + CastExpr( const CodeLocation & loc, const Expr * a, GeneratedFlag g = GeneratedCast, CastKind kind = Default ); /// Wrap a cast expression around an existing expression (always generated) Index: src/AST/SymbolTable.cpp =================================================================== --- src/AST/SymbolTable.cpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/AST/SymbolTable.cpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -19,4 +19,7 @@ #include "Copy.hpp" +#include +#include + #include "Decl.hpp" #include "Expr.hpp" @@ -195,4 +198,6 @@ out.push_back(decl.second); } + + // std::cerr << otypeKey << ' ' << out.size() << std::endl; } Index: src/AST/Type.hpp =================================================================== --- src/AST/Type.hpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/AST/Type.hpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -451,5 +451,7 @@ bool operator==(const TypeEnvKey & other) const; bool operator<(const TypeEnvKey & other) const; -}; + operator bool() {return base;} +}; + /// tuple type e.g. `[int, char]` Index: src/AST/TypeEnvironment.cpp =================================================================== --- src/AST/TypeEnvironment.cpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/AST/TypeEnvironment.cpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -135,5 +135,5 @@ } } - sub.normalize(); + // sub.normalize(); } Index: src/AST/TypeEnvironment.hpp =================================================================== --- src/AST/TypeEnvironment.hpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/AST/TypeEnvironment.hpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -63,5 +63,5 @@ int cmp = d1->var->name.compare( d2->var->name ); - return cmp < 0 || ( cmp == 0 && d1->result < d2->result ); + return cmp > 0 || ( cmp == 0 && d1->result < d2->result ); } }; Index: src/GenPoly/SpecializeNew.cpp =================================================================== --- src/GenPoly/SpecializeNew.cpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/GenPoly/SpecializeNew.cpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -113,7 +113,8 @@ using namespace ResolvExpr; ast::OpenVarSet openVars, closedVars; - ast::AssertionSet need, have; - findOpenVars( formalType, openVars, closedVars, need, have, FirstClosed ); - findOpenVars( actualType, openVars, closedVars, need, have, FirstOpen ); + ast::AssertionSet need, have; // unused + ast::TypeEnvironment env; // unused + // findOpenVars( formalType, openVars, closedVars, need, have, FirstClosed ); + findOpenVars( actualType, openVars, closedVars, need, have, env, FirstOpen ); for ( const ast::OpenVarSet::value_type & openVar : openVars ) { const ast::Type * boundType = subs->lookup( openVar.first ); @@ -125,4 +126,7 @@ if ( closedVars.find( *inst ) == closedVars.end() ) { return true; + } + else { + assertf(false, "closed: %s", inst->name.c_str()); } // Otherwise, the variable is bound to a concrete type. Index: src/Parser/ExpressionNode.cc =================================================================== --- src/Parser/ExpressionNode.cc (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/Parser/ExpressionNode.cc (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -601,5 +601,6 @@ ast::Expr * build_cast( const CodeLocation & location, DeclarationNode * decl_node, - ExpressionNode * expr_node ) { + ExpressionNode * expr_node, + ast::CastExpr::CastKind kind ) { ast::Type * targetType = maybeMoveBuildType( decl_node ); if ( dynamic_cast( targetType ) ) { @@ -607,10 +608,10 @@ return new ast::CastExpr( location, maybeMoveBuild( expr_node ), - ast::ExplicitCast ); + ast::ExplicitCast, kind ); } else { return new ast::CastExpr( location, maybeMoveBuild( expr_node ), targetType, - ast::ExplicitCast ); + ast::ExplicitCast, kind ); } // if } // build_cast Index: src/Parser/ExpressionNode.h =================================================================== --- src/Parser/ExpressionNode.h (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/Parser/ExpressionNode.h (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -69,5 +69,5 @@ ast::DimensionExpr * build_dimensionref( const CodeLocation &, const std::string * name ); -ast::Expr * build_cast( const CodeLocation &, DeclarationNode * decl_node, ExpressionNode * expr_node ); +ast::Expr * build_cast( const CodeLocation &, DeclarationNode * decl_node, ExpressionNode * expr_node, ast::CastExpr::CastKind kind = ast::CastExpr::Default ); ast::Expr * build_keyword_cast( const CodeLocation &, ast::AggregateDecl::Aggregate target, ExpressionNode * expr_node ); ast::Expr * build_virtual_cast( const CodeLocation &, DeclarationNode * decl_node, ExpressionNode * expr_node ); Index: src/Parser/parser.yy =================================================================== --- src/Parser/parser.yy (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/Parser/parser.yy (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -931,5 +931,5 @@ { $$ = new ExpressionNode( new ast::VirtualCastExpr( yylloc, maybeMoveBuild( $5 ), maybeMoveBuildType( $3 ) ) ); } | '(' RETURN type_no_function ')' cast_expression // CFA - { SemanticError( yylloc, "Return cast is currently unimplemented." ); $$ = nullptr; } + { $$ = new ExpressionNode( build_cast( yylloc, $3, $5, ast::CastExpr::Return ) ); } | '(' COERCE type_no_function ')' cast_expression // CFA { SemanticError( yylloc, "Coerce cast is currently unimplemented." ); $$ = nullptr; } Index: src/ResolvExpr/Candidate.hpp =================================================================== --- src/ResolvExpr/Candidate.hpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/Candidate.hpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -91,4 +91,5 @@ /// Holdover behaviour from old `findMinCost` -- xxx -- can maybe be eliminated? +/* static inline void promoteCvtCost( CandidateList & candidates ) { for ( CandidateRef & r : candidates ) { @@ -96,4 +97,5 @@ } } +*/ void print( std::ostream & os, const Candidate & cand, Indenter indent = {} ); Index: src/ResolvExpr/CandidateFinder.cpp =================================================================== --- src/ResolvExpr/CandidateFinder.cpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/CandidateFinder.cpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -25,16 +25,17 @@ #include "AdjustExprType.hpp" #include "Candidate.hpp" -#include "CastCost.hpp" // for castCost #include "CompilationState.h" -#include "ConversionCost.h" // for conversionCast #include "Cost.h" +#include "CastCost.hpp" +#include "PolyCost.hpp" +#include "SpecCost.hpp" +#include "ConversionCost.h" #include "ExplodedArg.hpp" -#include "PolyCost.hpp" #include "RenameVars.h" // for renameTyVars #include "Resolver.h" #include "ResolveTypeof.h" +#include "WidenMode.h" #include "SatisfyAssertions.hpp" -#include "SpecCost.hpp" -#include "typeops.h" // for combos +#include "typeops.h" // for adjustExprType, conversionCost, polyCost, specCost #include "Unify.h" #include "AST/Expr.hpp" @@ -55,1882 +56,4 @@ namespace ResolvExpr { -/// Unique identifier for matching expression resolutions to their requesting expression -UniqueId globalResnSlot = 0; - -namespace { - /// First index is which argument, second is which alternative, third is which exploded element - using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >; - - /// Returns a list of alternatives with the minimum cost in the given list - CandidateList findMinCost( const CandidateList & candidates ) { - CandidateList out; - Cost minCost = Cost::infinity; - for ( const CandidateRef & r : candidates ) { - if ( r->cost < minCost ) { - minCost = r->cost; - out.clear(); - out.emplace_back( r ); - } else if ( r->cost == minCost ) { - out.emplace_back( r ); - } - } - return out; - } - - /// Computes conversion cost for a given expression to a given type - const ast::Expr * computeExpressionConversionCost( - const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost - ) { - Cost convCost = computeConversionCost( - arg->result, paramType, arg->get_lvalue(), symtab, env ); - outCost += convCost; - - // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires - // conversion. Ignore poly cost for now, since this requires resolution of the cast to - // infer parameters and this does not currently work for the reason stated below - Cost tmpCost = convCost; - tmpCost.incPoly( -tmpCost.get_polyCost() ); - if ( tmpCost != Cost::zero ) { - ast::ptr< ast::Type > newType = paramType; - env.apply( newType ); - return new ast::CastExpr{ arg, newType }; - - // xxx - *should* be able to resolve this cast, but at the moment pointers are not - // castable to zero_t, but are implicitly convertible. This is clearly inconsistent, - // once this is fixed it should be possible to resolve the cast. - // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable, - // but it shouldn't be because this makes the conversion from DT* to DT* since - // commontype(zero_t, DT*) is DT*, rather than nothing - - // CandidateFinder finder{ symtab, env }; - // finder.find( arg, ResolvMode::withAdjustment() ); - // assertf( finder.candidates.size() > 0, - // "Somehow castable expression failed to find alternatives." ); - // assertf( finder.candidates.size() == 1, - // "Somehow got multiple alternatives for known cast expression." ); - // return finder.candidates.front()->expr; - } - - return arg; - } - - /// Computes conversion cost for a given candidate - Cost computeApplicationConversionCost( - CandidateRef cand, const ast::SymbolTable & symtab - ) { - auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >(); - auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); - auto function = pointer->base.strict_as< ast::FunctionType >(); - - Cost convCost = Cost::zero; - const auto & params = function->params; - auto param = params.begin(); - auto & args = appExpr->args; - - for ( unsigned i = 0; i < args.size(); ++i ) { - const ast::Type * argType = args[i]->result; - PRINT( - std::cerr << "arg expression:" << std::endl; - ast::print( std::cerr, args[i], 2 ); - std::cerr << "--- results are" << std::endl; - ast::print( std::cerr, argType, 2 ); - ) - - if ( param == params.end() ) { - if ( function->isVarArgs ) { - convCost.incUnsafe(); - PRINT( std::cerr << "end of params with varargs function: inc unsafe: " - << convCost << std::endl; ; ) - // convert reference-typed expressions into value-typed expressions - cand->expr = ast::mutate_field_index( - appExpr, &ast::ApplicationExpr::args, i, - referenceToRvalueConversion( args[i], convCost ) ); - continue; - } else return Cost::infinity; - } - - if ( auto def = args[i].as< ast::DefaultArgExpr >() ) { - // Default arguments should be free - don't include conversion cost. - // Unwrap them here because they are not relevant to the rest of the system - cand->expr = ast::mutate_field_index( - appExpr, &ast::ApplicationExpr::args, i, def->expr ); - ++param; - continue; - } - - // mark conversion cost and also specialization cost of param type - // const ast::Type * paramType = (*param)->get_type(); - cand->expr = ast::mutate_field_index( - appExpr, &ast::ApplicationExpr::args, i, - computeExpressionConversionCost( - args[i], *param, symtab, cand->env, convCost ) ); - convCost.decSpec( specCost( *param ) ); - ++param; // can't be in for-loop update because of the continue - } - - if ( param != params.end() ) return Cost::infinity; - - // specialization cost of return types can't be accounted for directly, it disables - // otherwise-identical calls, like this example based on auto-newline in the I/O lib: - // - // forall(otype OS) { - // void ?|?(OS&, int); // with newline - // OS& ?|?(OS&, int); // no newline, always chosen due to more specialization - // } - - // mark type variable and specialization cost of forall clause - convCost.incVar( function->forall.size() ); - convCost.decSpec( function->assertions.size() ); - - return convCost; - } - - void makeUnifiableVars( - const ast::FunctionType * type, ast::OpenVarSet & unifiableVars, - ast::AssertionSet & need - ) { - for ( auto & tyvar : type->forall ) { - unifiableVars[ *tyvar ] = ast::TypeData{ tyvar->base }; - } - for ( auto & assn : type->assertions ) { - need[ assn ].isUsed = true; - } - } - - /// Gets a default value from an initializer, nullptr if not present - const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) { - if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) { - if ( auto ce = si->value.as< ast::CastExpr >() ) { - return ce->arg.as< ast::ConstantExpr >(); - } else { - return si->value.as< ast::ConstantExpr >(); - } - } - return nullptr; - } - - /// State to iteratively build a match of parameter expressions to arguments - struct ArgPack { - std::size_t parent; ///< Index of parent pack - ast::ptr< ast::Expr > expr; ///< The argument stored here - Cost cost; ///< The cost of this argument - ast::TypeEnvironment env; ///< Environment for this pack - ast::AssertionSet need; ///< Assertions outstanding for this pack - ast::AssertionSet have; ///< Assertions found for this pack - ast::OpenVarSet open; ///< Open variables for this pack - unsigned nextArg; ///< Index of next argument in arguments list - unsigned tupleStart; ///< Number of tuples that start at this index - unsigned nextExpl; ///< Index of next exploded element - unsigned explAlt; ///< Index of alternative for nextExpl > 0 - - ArgPack() - : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ), - tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} - - ArgPack( - const ast::TypeEnvironment & env, const ast::AssertionSet & need, - const ast::AssertionSet & have, const ast::OpenVarSet & open ) - : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ), - open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} - - ArgPack( - std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env, - ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open, - unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero, - unsigned nextExpl = 0, unsigned explAlt = 0 ) - : parent(parent), expr( expr ), cost( cost ), env( std::move( env ) ), need( std::move( need ) ), - have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ), - nextExpl( nextExpl ), explAlt( explAlt ) {} - - ArgPack( - const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need, - ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added ) - : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( std::move( env ) ), - need( std::move( need ) ), have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ), - tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {} - - /// true if this pack is in the middle of an exploded argument - bool hasExpl() const { return nextExpl > 0; } - - /// Gets the list of exploded candidates for this pack - const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const { - return args[ nextArg-1 ][ explAlt ]; - } - - /// Ends a tuple expression, consolidating the appropriate args - void endTuple( const std::vector< ArgPack > & packs ) { - // add all expressions in tuple to list, summing cost - std::deque< const ast::Expr * > exprs; - const ArgPack * pack = this; - if ( expr ) { exprs.emplace_front( expr ); } - while ( pack->tupleStart == 0 ) { - pack = &packs[pack->parent]; - exprs.emplace_front( pack->expr ); - cost += pack->cost; - } - // reset pack to appropriate tuple - std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() ); - expr = new ast::TupleExpr{ expr->location, std::move( exprv ) }; - tupleStart = pack->tupleStart - 1; - parent = pack->parent; - } - }; - - /// Instantiates an argument to match a parameter, returns false if no matching results left - bool instantiateArgument( - const CodeLocation & location, - const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args, - std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab, - unsigned nTuples = 0 - ) { - if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) { - // paramType is a TupleType -- group args into a TupleExpr - ++nTuples; - for ( const ast::Type * type : *tupleType ) { - // xxx - dropping initializer changes behaviour from previous, but seems correct - // ^^^ need to handle the case where a tuple has a default argument - if ( ! instantiateArgument( location, - type, nullptr, args, results, genStart, symtab, nTuples ) ) return false; - nTuples = 0; - } - // re-constitute tuples for final generation - for ( auto i = genStart; i < results.size(); ++i ) { - results[i].endTuple( results ); - } - return true; - } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) { - // paramType is a ttype, consumes all remaining arguments - - // completed tuples; will be spliced to end of results to finish - std::vector< ArgPack > finalResults{}; - - // iterate until all results completed - std::size_t genEnd; - ++nTuples; - do { - genEnd = results.size(); - - // add another argument to results - for ( std::size_t i = genStart; i < genEnd; ++i ) { - unsigned nextArg = results[i].nextArg; - - // use next element of exploded tuple if present - if ( results[i].hasExpl() ) { - const ExplodedArg & expl = results[i].getExpl( args ); - - unsigned nextExpl = results[i].nextExpl + 1; - if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } - - results.emplace_back( - i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ), - copy( results[i].need ), copy( results[i].have ), - copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl, - results[i].explAlt ); - - continue; - } - - // finish result when out of arguments - if ( nextArg >= args.size() ) { - ArgPack newResult{ - results[i].env, results[i].need, results[i].have, results[i].open }; - newResult.nextArg = nextArg; - const ast::Type * argType = nullptr; - - if ( nTuples > 0 || ! results[i].expr ) { - // first iteration or no expression to clone, - // push empty tuple expression - newResult.parent = i; - newResult.expr = new ast::TupleExpr( location, {} ); - argType = newResult.expr->result; - } else { - // clone result to collect tuple - newResult.parent = results[i].parent; - newResult.cost = results[i].cost; - newResult.tupleStart = results[i].tupleStart; - newResult.expr = results[i].expr; - argType = newResult.expr->result; - - if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) { - // the case where a ttype value is passed directly is special, - // e.g. for argument forwarding purposes - // xxx - what if passing multiple arguments, last of which is - // ttype? - // xxx - what would happen if unify was changed so that unifying - // tuple - // types flattened both before unifying lists? then pass in - // TupleType (ttype) below. - --newResult.tupleStart; - } else { - // collapse leftover arguments into tuple - newResult.endTuple( results ); - argType = newResult.expr->result; - } - } - - // check unification for ttype before adding to final - if ( - unify( - ttype, argType, newResult.env, newResult.need, newResult.have, - newResult.open ) - ) { - finalResults.emplace_back( std::move( newResult ) ); - } - - continue; - } - - // add each possible next argument - for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { - const ExplodedArg & expl = args[nextArg][j]; - - // fresh copies of parent parameters for this iteration - ast::TypeEnvironment env = results[i].env; - ast::OpenVarSet open = results[i].open; - - env.addActual( expl.env, open ); - - // skip empty tuple arguments by (nearly) cloning parent into next gen - if ( expl.exprs.empty() ) { - results.emplace_back( - results[i], std::move( env ), copy( results[i].need ), - copy( results[i].have ), std::move( open ), nextArg + 1, expl.cost ); - - continue; - } - - // add new result - results.emplace_back( - i, expl.exprs.front(), std::move( env ), copy( results[i].need ), - copy( results[i].have ), std::move( open ), nextArg + 1, nTuples, - expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); - } - } - - // reset for next round - genStart = genEnd; - nTuples = 0; - } while ( genEnd != results.size() ); - - // splice final results onto results - for ( std::size_t i = 0; i < finalResults.size(); ++i ) { - results.emplace_back( std::move( finalResults[i] ) ); - } - return ! finalResults.empty(); - } - - // iterate each current subresult - std::size_t genEnd = results.size(); - for ( std::size_t i = genStart; i < genEnd; ++i ) { - unsigned nextArg = results[i].nextArg; - - // use remainder of exploded tuple if present - if ( results[i].hasExpl() ) { - const ExplodedArg & expl = results[i].getExpl( args ); - const ast::Expr * expr = expl.exprs[ results[i].nextExpl ]; - - ast::TypeEnvironment env = results[i].env; - ast::AssertionSet need = results[i].need, have = results[i].have; - ast::OpenVarSet open = results[i].open; - - const ast::Type * argType = expr->result; - - PRINT( - std::cerr << "param type is "; - ast::print( std::cerr, paramType ); - std::cerr << std::endl << "arg type is "; - ast::print( std::cerr, argType ); - std::cerr << std::endl; - ) - - if ( unify( paramType, argType, env, need, have, open ) ) { - unsigned nextExpl = results[i].nextExpl + 1; - if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } - - results.emplace_back( - i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), nextArg, - nTuples, Cost::zero, nextExpl, results[i].explAlt ); - } - - continue; - } - - // use default initializers if out of arguments - if ( nextArg >= args.size() ) { - if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) { - ast::TypeEnvironment env = results[i].env; - ast::AssertionSet need = results[i].need, have = results[i].have; - ast::OpenVarSet open = results[i].open; - - if ( unify( paramType, cnst->result, env, need, have, open ) ) { - results.emplace_back( - i, new ast::DefaultArgExpr{ cnst->location, cnst }, std::move( env ), - std::move( need ), std::move( have ), std::move( open ), nextArg, nTuples ); - } - } - - continue; - } - - // Check each possible next argument - for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { - const ExplodedArg & expl = args[nextArg][j]; - - // fresh copies of parent parameters for this iteration - ast::TypeEnvironment env = results[i].env; - ast::AssertionSet need = results[i].need, have = results[i].have; - ast::OpenVarSet open = results[i].open; - - env.addActual( expl.env, open ); - - // skip empty tuple arguments by (nearly) cloning parent into next gen - if ( expl.exprs.empty() ) { - results.emplace_back( - results[i], std::move( env ), std::move( need ), std::move( have ), std::move( open ), - nextArg + 1, expl.cost ); - - continue; - } - - // consider only first exploded arg - const ast::Expr * expr = expl.exprs.front(); - const ast::Type * argType = expr->result; - - PRINT( - std::cerr << "param type is "; - ast::print( std::cerr, paramType ); - std::cerr << std::endl << "arg type is "; - ast::print( std::cerr, argType ); - std::cerr << std::endl; - ) - - // attempt to unify types - if ( unify( paramType, argType, env, need, have, open ) ) { - // add new result - results.emplace_back( - i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), - nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); - } - } - } - - // reset for next parameter - genStart = genEnd; - - return genEnd != results.size(); // were any new results added? - } - - /// Generate a cast expression from `arg` to `toType` - const ast::Expr * restructureCast( - ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast - ) { - if ( - arg->result->size() > 1 - && ! toType->isVoid() - && ! dynamic_cast< const ast::ReferenceType * >( toType ) - ) { - // Argument is a tuple and the target type is neither void nor a reference. Cast each - // member of the tuple to its corresponding target type, producing the tuple of those - // cast expressions. If there are more components of the tuple than components in the - // target type, then excess components do not come out in the result expression (but - // UniqueExpr ensures that the side effects will still be produced) - if ( Tuples::maybeImpureIgnoreUnique( arg ) ) { - // expressions which may contain side effects require a single unique instance of - // the expression - arg = new ast::UniqueExpr{ arg->location, arg }; - } - std::vector< ast::ptr< ast::Expr > > components; - for ( unsigned i = 0; i < toType->size(); ++i ) { - // cast each component - ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i }; - components.emplace_back( - restructureCast( idx, toType->getComponent( i ), isGenerated ) ); - } - return new ast::TupleExpr{ arg->location, std::move( components ) }; - } else { - // handle normally - return new ast::CastExpr{ arg->location, arg, toType, isGenerated }; - } - } - - /// Gets the name from an untyped member expression (must be NameExpr) - const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) { - if ( memberExpr->member.as< ast::ConstantExpr >() ) { - SemanticError( memberExpr, "Indexed access to struct fields unsupported: " ); - } - - return memberExpr->member.strict_as< ast::NameExpr >()->name; - } - - /// Actually visits expressions to find their candidate interpretations - class Finder final : public ast::WithShortCircuiting { - const ResolveContext & context; - const ast::SymbolTable & symtab; - public: - // static size_t traceId; - CandidateFinder & selfFinder; - CandidateList & candidates; - const ast::TypeEnvironment & tenv; - ast::ptr< ast::Type > & targetType; - - enum Errors { - NotFound, - NoMatch, - ArgsToFew, - ArgsToMany, - RetsToFew, - RetsToMany, - NoReason - }; - - struct { - Errors code = NotFound; - } reason; - - Finder( CandidateFinder & f ) - : context( f.context ), symtab( context.symtab ), selfFinder( f ), - candidates( f.candidates ), tenv( f.env ), targetType( f.targetType ) {} - - void previsit( const ast::Node * ) { visit_children = false; } - - /// Convenience to add candidate to list - template - void addCandidate( Args &&... args ) { - candidates.emplace_back( new Candidate{ std::forward( args )... } ); - reason.code = NoReason; - } - - void postvisit( const ast::ApplicationExpr * applicationExpr ) { - addCandidate( applicationExpr, tenv ); - } - - /// Set up candidate assertions for inference - void inferParameters( CandidateRef & newCand, CandidateList & out ); - - /// Completes a function candidate with arguments located - void validateFunctionCandidate( - const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, - CandidateList & out ); - - /// Builds a list of candidates for a function, storing them in out - void makeFunctionCandidates( - const CodeLocation & location, - const CandidateRef & func, const ast::FunctionType * funcType, - const ExplodedArgs_new & args, CandidateList & out ); - - /// Adds implicit struct-conversions to the alternative list - void addAnonConversions( const CandidateRef & cand ); - - /// Adds aggregate member interpretations - void addAggMembers( - const ast::BaseInstType * aggrInst, const ast::Expr * expr, - const Candidate & cand, const Cost & addedCost, const std::string & name - ); - - /// Adds tuple member interpretations - void addTupleMembers( - const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, - const Cost & addedCost, const ast::Expr * member - ); - - /// true if expression is an lvalue - static bool isLvalue( const ast::Expr * x ) { - return x->result && ( x->get_lvalue() || x->result.as< ast::ReferenceType >() ); - } - - void postvisit( const ast::UntypedExpr * untypedExpr ); - void postvisit( const ast::VariableExpr * variableExpr ); - void postvisit( const ast::ConstantExpr * constantExpr ); - void postvisit( const ast::SizeofExpr * sizeofExpr ); - void postvisit( const ast::AlignofExpr * alignofExpr ); - void postvisit( const ast::AddressExpr * addressExpr ); - void postvisit( const ast::LabelAddressExpr * labelExpr ); - void postvisit( const ast::CastExpr * castExpr ); - void postvisit( const ast::VirtualCastExpr * castExpr ); - void postvisit( const ast::KeywordCastExpr * castExpr ); - void postvisit( const ast::UntypedMemberExpr * memberExpr ); - void postvisit( const ast::MemberExpr * memberExpr ); - void postvisit( const ast::NameExpr * nameExpr ); - void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ); - void postvisit( const ast::OffsetofExpr * offsetofExpr ); - void postvisit( const ast::OffsetPackExpr * offsetPackExpr ); - void postvisit( const ast::LogicalExpr * logicalExpr ); - void postvisit( const ast::ConditionalExpr * conditionalExpr ); - void postvisit( const ast::CommaExpr * commaExpr ); - void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ); - void postvisit( const ast::ConstructorExpr * ctorExpr ); - void postvisit( const ast::RangeExpr * rangeExpr ); - void postvisit( const ast::UntypedTupleExpr * tupleExpr ); - void postvisit( const ast::TupleExpr * tupleExpr ); - void postvisit( const ast::TupleIndexExpr * tupleExpr ); - void postvisit( const ast::TupleAssignExpr * tupleExpr ); - void postvisit( const ast::UniqueExpr * unqExpr ); - void postvisit( const ast::StmtExpr * stmtExpr ); - void postvisit( const ast::UntypedInitExpr * initExpr ); - - void postvisit( const ast::InitExpr * ) { - assertf( false, "CandidateFinder should never see a resolved InitExpr." ); - } - - void postvisit( const ast::DeletedExpr * ) { - assertf( false, "CandidateFinder should never see a DeletedExpr." ); - } - - void postvisit( const ast::GenericExpr * ) { - assertf( false, "_Generic is not yet supported." ); - } - }; - - /// Set up candidate assertions for inference - void Finder::inferParameters( CandidateRef & newCand, CandidateList & out ) { - // Set need bindings for any unbound assertions - UniqueId crntResnSlot = 0; // matching ID for this expression's assertions - for ( auto & assn : newCand->need ) { - // skip already-matched assertions - if ( assn.second.resnSlot != 0 ) continue; - // assign slot for expression if needed - if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; } - // fix slot to assertion - assn.second.resnSlot = crntResnSlot; - } - // pair slot to expression - if ( crntResnSlot != 0 ) { - newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot ); - } - - // add to output list; assertion satisfaction will occur later - out.emplace_back( newCand ); - } - - /// Completes a function candidate with arguments located - void Finder::validateFunctionCandidate( - const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, - CandidateList & out - ) { - ast::ApplicationExpr * appExpr = - new ast::ApplicationExpr{ func->expr->location, func->expr }; - // sum cost and accumulate arguments - std::deque< const ast::Expr * > args; - Cost cost = func->cost; - const ArgPack * pack = &result; - while ( pack->expr ) { - args.emplace_front( pack->expr ); - cost += pack->cost; - pack = &results[pack->parent]; - } - std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() ); - appExpr->args = std::move( vargs ); - // build and validate new candidate - auto newCand = - std::make_shared( appExpr, result.env, result.open, result.need, cost ); - PRINT( - std::cerr << "instantiate function success: " << appExpr << std::endl; - std::cerr << "need assertions:" << std::endl; - ast::print( std::cerr, result.need, 2 ); - ) - inferParameters( newCand, out ); - } - - /// Builds a list of candidates for a function, storing them in out - void Finder::makeFunctionCandidates( - const CodeLocation & location, - const CandidateRef & func, const ast::FunctionType * funcType, - const ExplodedArgs_new & args, CandidateList & out - ) { - ast::OpenVarSet funcOpen; - ast::AssertionSet funcNeed, funcHave; - ast::TypeEnvironment funcEnv{ func->env }; - makeUnifiableVars( funcType, funcOpen, funcNeed ); - // add all type variables as open variables now so that those not used in the - // parameter list are still considered open - funcEnv.add( funcType->forall ); - - if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) { - // attempt to narrow based on expected target type - const ast::Type * returnType = funcType->returns.front(); - if ( ! unify( - returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen ) - ) { - // unification failed, do not pursue this candidate - return; - } - } - - // iteratively build matches, one parameter at a time - std::vector< ArgPack > results; - results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen ); - std::size_t genStart = 0; - - // xxx - how to handle default arg after change to ftype representation? - if (const ast::VariableExpr * varExpr = func->expr.as()) { - if (const ast::FunctionDecl * funcDecl = varExpr->var.as()) { - // function may have default args only if directly calling by name - // must use types on candidate however, due to RenameVars substitution - auto nParams = funcType->params.size(); - - for (size_t i=0; iparams[i].strict_as(); - if (!instantiateArgument( location, - funcType->params[i], obj->init, args, results, genStart, symtab)) return; - } - goto endMatch; - } - } - for ( const auto & param : funcType->params ) { - // Try adding the arguments corresponding to the current parameter to the existing - // matches - // no default args for indirect calls - if ( ! instantiateArgument( location, - param, nullptr, args, results, genStart, symtab ) ) return; - } - - endMatch: - if ( funcType->isVarArgs ) { - // append any unused arguments to vararg pack - std::size_t genEnd; - do { - genEnd = results.size(); - - // iterate results - for ( std::size_t i = genStart; i < genEnd; ++i ) { - unsigned nextArg = results[i].nextArg; - - // use remainder of exploded tuple if present - if ( results[i].hasExpl() ) { - const ExplodedArg & expl = results[i].getExpl( args ); - - unsigned nextExpl = results[i].nextExpl + 1; - if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } - - results.emplace_back( - i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ), - copy( results[i].need ), copy( results[i].have ), - copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl, - results[i].explAlt ); - - continue; - } - - // finish result when out of arguments - if ( nextArg >= args.size() ) { - validateFunctionCandidate( func, results[i], results, out ); - - continue; - } - - // add each possible next argument - for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { - const ExplodedArg & expl = args[nextArg][j]; - - // fresh copies of parent parameters for this iteration - ast::TypeEnvironment env = results[i].env; - ast::OpenVarSet open = results[i].open; - - env.addActual( expl.env, open ); - - // skip empty tuple arguments by (nearly) cloning parent into next gen - if ( expl.exprs.empty() ) { - results.emplace_back( - results[i], std::move( env ), copy( results[i].need ), - copy( results[i].have ), std::move( open ), nextArg + 1, - expl.cost ); - - continue; - } - - // add new result - results.emplace_back( - i, expl.exprs.front(), std::move( env ), copy( results[i].need ), - copy( results[i].have ), std::move( open ), nextArg + 1, 0, expl.cost, - expl.exprs.size() == 1 ? 0 : 1, j ); - } - } - - genStart = genEnd; - } while( genEnd != results.size() ); - } else { - // filter out the results that don't use all the arguments - for ( std::size_t i = genStart; i < results.size(); ++i ) { - ArgPack & result = results[i]; - if ( ! result.hasExpl() && result.nextArg >= args.size() ) { - validateFunctionCandidate( func, result, results, out ); - } - } - } - } - - /// Adds implicit struct-conversions to the alternative list - void Finder::addAnonConversions( const CandidateRef & cand ) { - // adds anonymous member interpretations whenever an aggregate value type is seen. - // it's okay for the aggregate expression to have reference type -- cast it to the - // base type to treat the aggregate as the referenced value - ast::ptr< ast::Expr > aggrExpr( cand->expr ); - ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result; - cand->env.apply( aggrType ); - - if ( aggrType.as< ast::ReferenceType >() ) { - aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() }; - } - - if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) { - addAggMembers( structInst, aggrExpr, *cand, Cost::safe, "" ); - } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) { - addAggMembers( unionInst, aggrExpr, *cand, Cost::safe, "" ); - } - } - - /// Adds aggregate member interpretations - void Finder::addAggMembers( - const ast::BaseInstType * aggrInst, const ast::Expr * expr, - const Candidate & cand, const Cost & addedCost, const std::string & name - ) { - for ( const ast::Decl * decl : aggrInst->lookup( name ) ) { - auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl ); - CandidateRef newCand = std::make_shared( - cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost ); - // add anonymous member interpretations whenever an aggregate value type is seen - // as a member expression - addAnonConversions( newCand ); - candidates.emplace_back( std::move( newCand ) ); - } - } - - /// Adds tuple member interpretations - void Finder::addTupleMembers( - const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, - const Cost & addedCost, const ast::Expr * member - ) { - if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) { - // get the value of the constant expression as an int, must be between 0 and the - // length of the tuple to have meaning - long long val = constantExpr->intValue(); - if ( val >= 0 && (unsigned long long)val < tupleType->size() ) { - addCandidate( - cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val }, - addedCost ); - } - } - } - - void Finder::postvisit( const ast::UntypedExpr * untypedExpr ) { - std::vector< CandidateFinder > argCandidates = - selfFinder.findSubExprs( untypedExpr->args ); - - // take care of possible tuple assignments - // if not tuple assignment, handled as normal function call - Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates ); - - CandidateFinder funcFinder( context, tenv ); - if (auto nameExpr = untypedExpr->func.as()) { - auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name); - if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) { - assertf(!argCandidates.empty(), "special function call without argument"); - for (auto & firstArgCand: argCandidates[0]) { - ast::ptr argType = firstArgCand->expr->result; - firstArgCand->env.apply(argType); - // strip references - // xxx - is this correct? - while (argType.as()) argType = argType.as()->base; - - // convert 1-tuple to plain type - if (auto tuple = argType.as()) { - if (tuple->size() == 1) { - argType = tuple->types[0]; - } - } - - // if argType is an unbound type parameter, all special functions need to be searched. - if (isUnboundType(argType)) { - funcFinder.otypeKeys.clear(); - break; - } - - if (argType.as()) funcFinder.otypeKeys.insert(Mangle::Encoding::pointer); - // else if (const ast::EnumInstType * enumInst = argType.as()) { - // const ast::EnumDecl * enumDecl = enumInst->base; // Here - // if ( const ast::Type* enumType = enumDecl->base ) { - // // instance of enum (T) is a instance of type (T) - // funcFinder.otypeKeys.insert(Mangle::mangle(enumType, Mangle::NoGenericParams | Mangle::Type)); - // } else { - // // instance of an untyped enum is techically int - // funcFinder.otypeKeys.insert(Mangle::mangle(enumDecl, Mangle::NoGenericParams | Mangle::Type)); - // } - // } - else funcFinder.otypeKeys.insert(Mangle::mangle(argType, Mangle::NoGenericParams | Mangle::Type)); - } - } - } - // if candidates are already produced, do not fail - // xxx - is it possible that handleTupleAssignment and main finder both produce candidates? - // this means there exists ctor/assign functions with a tuple as first parameter. - ResolvMode mode = { - true, // adjust - !untypedExpr->func.as(), // prune if not calling by name - selfFinder.candidates.empty() // failfast if other options are not found - }; - funcFinder.find( untypedExpr->func, mode ); - // short-circuit if no candidates - // if ( funcFinder.candidates.empty() ) return; - - reason.code = NoMatch; - - // find function operators - ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" }; // ??? why not ?{} - CandidateFinder opFinder( context, tenv ); - // okay if there aren't any function operations - opFinder.find( opExpr, ResolvMode::withoutFailFast() ); - PRINT( - std::cerr << "known function ops:" << std::endl; - print( std::cerr, opFinder.candidates, 1 ); - ) - - // pre-explode arguments - ExplodedArgs_new argExpansions; - for ( const CandidateFinder & args : argCandidates ) { - argExpansions.emplace_back(); - auto & argE = argExpansions.back(); - for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); } - } - - // Find function matches - CandidateList found; - SemanticErrorException errors; - for ( CandidateRef & func : funcFinder ) { - try { - PRINT( - std::cerr << "working on alternative:" << std::endl; - print( std::cerr, *func, 2 ); - ) - - // check if the type is a pointer to function - const ast::Type * funcResult = func->expr->result->stripReferences(); - if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) { - if ( auto function = pointer->base.as< ast::FunctionType >() ) { - CandidateRef newFunc{ new Candidate{ *func } }; - newFunc->expr = - referenceToRvalueConversion( newFunc->expr, newFunc->cost ); - makeFunctionCandidates( untypedExpr->location, - newFunc, function, argExpansions, found ); - } - } else if ( - auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) - ) { - if ( const ast::EqvClass * clz = func->env.lookup( *inst ) ) { - if ( auto function = clz->bound.as< ast::FunctionType >() ) { - CandidateRef newFunc{ new Candidate{ *func } }; - newFunc->expr = - referenceToRvalueConversion( newFunc->expr, newFunc->cost ); - makeFunctionCandidates( untypedExpr->location, - newFunc, function, argExpansions, found ); - } - } - } - } catch ( SemanticErrorException & e ) { errors.append( e ); } - } - - // Find matches on function operators `?()` - if ( ! opFinder.candidates.empty() ) { - // add exploded function alternatives to front of argument list - std::vector< ExplodedArg > funcE; - funcE.reserve( funcFinder.candidates.size() ); - for ( const CandidateRef & func : funcFinder ) { - funcE.emplace_back( *func, symtab ); - } - argExpansions.emplace_front( std::move( funcE ) ); - - for ( const CandidateRef & op : opFinder ) { - try { - // check if type is pointer-to-function - const ast::Type * opResult = op->expr->result->stripReferences(); - if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) { - if ( auto function = pointer->base.as< ast::FunctionType >() ) { - CandidateRef newOp{ new Candidate{ *op} }; - newOp->expr = - referenceToRvalueConversion( newOp->expr, newOp->cost ); - makeFunctionCandidates( untypedExpr->location, - newOp, function, argExpansions, found ); - } - } - } catch ( SemanticErrorException & e ) { errors.append( e ); } - } - } - - // Implement SFINAE; resolution errors are only errors if there aren't any non-error - // candidates - if ( found.empty() && ! errors.isEmpty() ) { throw errors; } - - // Compute conversion costs - for ( CandidateRef & withFunc : found ) { - Cost cvtCost = computeApplicationConversionCost( withFunc, symtab ); - - PRINT( - auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >(); - auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); - auto function = pointer->base.strict_as< ast::FunctionType >(); - - std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl; - std::cerr << "parameters are:" << std::endl; - ast::printAll( std::cerr, function->params, 2 ); - std::cerr << "arguments are:" << std::endl; - ast::printAll( std::cerr, appExpr->args, 2 ); - std::cerr << "bindings are:" << std::endl; - ast::print( std::cerr, withFunc->env, 2 ); - std::cerr << "cost is: " << withFunc->cost << std::endl; - std::cerr << "cost of conversion is:" << cvtCost << std::endl; - ) - - if ( cvtCost != Cost::infinity ) { - withFunc->cvtCost = cvtCost; - candidates.emplace_back( std::move( withFunc ) ); - } - } - found = std::move( candidates ); - - // use a new list so that candidates are not examined by addAnonConversions twice - CandidateList winners = findMinCost( found ); - promoteCvtCost( winners ); - - // function may return a struct/union value, in which case we need to add candidates - // for implicit conversions to each of the anonymous members, which must happen after - // `findMinCost`, since anon conversions are never the cheapest - for ( const CandidateRef & c : winners ) { - addAnonConversions( c ); - } - spliceBegin( candidates, winners ); - - if ( candidates.empty() && targetType && ! targetType->isVoid() ) { - // If resolution is unsuccessful with a target type, try again without, since it - // will sometimes succeed when it wouldn't with a target type binding. - // For example: - // forall( otype T ) T & ?[]( T *, ptrdiff_t ); - // const char * x = "hello world"; - // unsigned char ch = x[0]; - // Fails with simple return type binding (xxx -- check this!) as follows: - // * T is bound to unsigned char - // * (x: const char *) is unified with unsigned char *, which fails - // xxx -- fix this better - targetType = nullptr; - postvisit( untypedExpr ); - } - } - - void Finder::postvisit( const ast::AddressExpr * addressExpr ) { - CandidateFinder finder( context, tenv ); - finder.find( addressExpr->arg ); - - if ( finder.candidates.empty() ) return; - - reason.code = NoMatch; - - for ( CandidateRef & r : finder.candidates ) { - if ( ! isLvalue( r->expr ) ) continue; - addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } ); - } - } - - void Finder::postvisit( const ast::LabelAddressExpr * labelExpr ) { - addCandidate( labelExpr, tenv ); - } - - void Finder::postvisit( const ast::CastExpr * castExpr ) { - ast::ptr< ast::Type > toType = castExpr->result; - assert( toType ); - toType = resolveTypeof( toType, context ); - toType = adjustExprType( toType, tenv, symtab ); - - CandidateFinder finder( context, tenv, toType ); - finder.find( castExpr->arg, ResolvMode::withAdjustment() ); - - if ( !finder.candidates.empty() ) reason.code = NoMatch; - - CandidateList matches; - for ( CandidateRef & cand : finder.candidates ) { - ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have; - ast::OpenVarSet open( cand->open ); - - cand->env.extractOpenVars( open ); - - // It is possible that a cast can throw away some values in a multiply-valued - // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the - // subexpression results that are cast directly. The candidate is invalid if it - // has fewer results than there are types to cast to. - int discardedValues = cand->expr->result->size() - toType->size(); - if ( discardedValues < 0 ) continue; - - // unification run for side-effects - unify( toType, cand->expr->result, cand->env, need, have, open ); - Cost thisCost = - (castExpr->isGenerated == ast::GeneratedFlag::GeneratedCast) - ? conversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env ) - : castCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env ); - - PRINT( - std::cerr << "working on cast with result: " << toType << std::endl; - std::cerr << "and expr type: " << cand->expr->result << std::endl; - std::cerr << "env: " << cand->env << std::endl; - ) - if ( thisCost != Cost::infinity ) { - PRINT( - std::cerr << "has finite cost." << std::endl; - ) - // count one safe conversion for each value that is thrown away - thisCost.incSafe( discardedValues ); - CandidateRef newCand = std::make_shared( - restructureCast( cand->expr, toType, castExpr->isGenerated ), - copy( cand->env ), std::move( open ), std::move( need ), cand->cost, - cand->cost + thisCost ); - inferParameters( newCand, matches ); - } - } - - // select first on argument cost, then conversion cost - CandidateList minArgCost = findMinCost( matches ); - promoteCvtCost( minArgCost ); - candidates = findMinCost( minArgCost ); - } - - void Finder::postvisit( const ast::VirtualCastExpr * castExpr ) { - assertf( castExpr->result, "Implicit virtual cast targets not yet supported." ); - CandidateFinder finder( context, tenv ); - // don't prune here, all alternatives guaranteed to have same type - finder.find( castExpr->arg, ResolvMode::withoutPrune() ); - for ( CandidateRef & r : finder.candidates ) { - addCandidate( - *r, - new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } ); - } - } - - void Finder::postvisit( const ast::KeywordCastExpr * castExpr ) { - const auto & loc = castExpr->location; - assertf( castExpr->result, "Cast target should have been set in Validate." ); - auto ref = castExpr->result.strict_as(); - auto inst = ref->base.strict_as(); - auto target = inst->base.get(); - - CandidateFinder finder( context, tenv ); - - auto pick_alternatives = [target, this](CandidateList & found, bool expect_ref) { - for (auto & cand : found) { - const ast::Type * expr = cand->expr->result.get(); - if (expect_ref) { - auto res = dynamic_cast(expr); - if (!res) { continue; } - expr = res->base.get(); - } - - if (auto insttype = dynamic_cast(expr)) { - auto td = cand->env.lookup(*insttype); - if (!td) { continue; } - expr = td->bound.get(); - } - - if (auto base = dynamic_cast(expr)) { - if (base->base == target) { - candidates.push_back( std::move(cand) ); - reason.code = NoReason; - } - } - } - }; - - try { - // Attempt 1 : turn (thread&)X into (thread$&)X.__thrd - // Clone is purely for memory management - std::unique_ptr tech1 { new ast::UntypedMemberExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.field), castExpr->arg) }; - - // don't prune here, since it's guaranteed all alternatives will have the same type - finder.find( tech1.get(), ResolvMode::withoutPrune() ); - pick_alternatives(finder.candidates, false); - - return; - } catch(SemanticErrorException & ) {} - - // Fallback : turn (thread&)X into (thread$&)get_thread(X) - std::unique_ptr fallback { ast::UntypedExpr::createDeref(loc, new ast::UntypedExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.getter), { castExpr->arg })) }; - // don't prune here, since it's guaranteed all alternatives will have the same type - finder.find( fallback.get(), ResolvMode::withoutPrune() ); - - pick_alternatives(finder.candidates, true); - - // Whatever happens here, we have no more fallbacks - } - - void Finder::postvisit( const ast::UntypedMemberExpr * memberExpr ) { - CandidateFinder aggFinder( context, tenv ); - aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() ); - for ( CandidateRef & agg : aggFinder.candidates ) { - // it's okay for the aggregate expression to have reference type -- cast it to the - // base type to treat the aggregate as the referenced value - Cost addedCost = Cost::zero; - agg->expr = referenceToRvalueConversion( agg->expr, addedCost ); - - // find member of the given type - if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) { - addAggMembers( - structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); - } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) { - addAggMembers( - unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); - } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) { - addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member ); - } - } - } - - void Finder::postvisit( const ast::MemberExpr * memberExpr ) { - addCandidate( memberExpr, tenv ); - } - - void Finder::postvisit( const ast::NameExpr * nameExpr ) { - std::vector< ast::SymbolTable::IdData > declList; - if (!selfFinder.otypeKeys.empty()) { - auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name); - assertf(kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS, "special lookup with non-special target: %s", nameExpr->name.c_str()); - - for (auto & otypeKey: selfFinder.otypeKeys) { - auto result = symtab.specialLookupId(kind, otypeKey); - declList.insert(declList.end(), std::make_move_iterator(result.begin()), std::make_move_iterator(result.end())); - } - } else { - declList = symtab.lookupId( nameExpr->name ); - } - PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; ) - - if ( declList.empty() ) return; - - reason.code = NoMatch; - - for ( auto & data : declList ) { - Cost cost = Cost::zero; - ast::Expr * newExpr = data.combine( nameExpr->location, cost ); - - CandidateRef newCand = std::make_shared( - newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero, - cost ); - - if (newCand->expr->env) { - newCand->env.add(*newCand->expr->env); - auto mutExpr = newCand->expr.get_and_mutate(); - mutExpr->env = nullptr; - newCand->expr = mutExpr; - } - - PRINT( - std::cerr << "decl is "; - ast::print( std::cerr, data.id ); - std::cerr << std::endl; - std::cerr << "newExpr is "; - ast::print( std::cerr, newExpr ); - std::cerr << std::endl; - ) - newCand->expr = ast::mutate_field( - newCand->expr.get(), &ast::Expr::result, - renameTyVars( newCand->expr->result ) ); - // add anonymous member interpretations whenever an aggregate value type is seen - // as a name expression - addAnonConversions( newCand ); - candidates.emplace_back( std::move( newCand ) ); - } - } - - void Finder::postvisit( const ast::VariableExpr * variableExpr ) { - // not sufficient to just pass `variableExpr` here, type might have changed since - // creation - addCandidate( - new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv ); - } - - void Finder::postvisit( const ast::ConstantExpr * constantExpr ) { - addCandidate( constantExpr, tenv ); - } - - void Finder::postvisit( const ast::SizeofExpr * sizeofExpr ) { - if ( sizeofExpr->type ) { - addCandidate( - new ast::SizeofExpr{ - sizeofExpr->location, resolveTypeof( sizeofExpr->type, context ) }, - tenv ); - } else { - // find all candidates for the argument to sizeof - CandidateFinder finder( context, tenv ); - finder.find( sizeofExpr->expr ); - // find the lowest-cost candidate, otherwise ambiguous - CandidateList winners = findMinCost( finder.candidates ); - if ( winners.size() != 1 ) { - SemanticError( - sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " ); - } - // return the lowest-cost candidate - CandidateRef & choice = winners.front(); - choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); - choice->cost = Cost::zero; - addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } ); - } - } - - void Finder::postvisit( const ast::AlignofExpr * alignofExpr ) { - if ( alignofExpr->type ) { - addCandidate( - new ast::AlignofExpr{ - alignofExpr->location, resolveTypeof( alignofExpr->type, context ) }, - tenv ); - } else { - // find all candidates for the argument to alignof - CandidateFinder finder( context, tenv ); - finder.find( alignofExpr->expr ); - // find the lowest-cost candidate, otherwise ambiguous - CandidateList winners = findMinCost( finder.candidates ); - if ( winners.size() != 1 ) { - SemanticError( - alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " ); - } - // return the lowest-cost candidate - CandidateRef & choice = winners.front(); - choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); - choice->cost = Cost::zero; - addCandidate( - *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } ); - } - } - - void Finder::postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) { - const ast::BaseInstType * aggInst; - if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ; - else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ; - else return; - - for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) { - auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member ); - addCandidate( - new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv ); - } - } - - void Finder::postvisit( const ast::OffsetofExpr * offsetofExpr ) { - addCandidate( offsetofExpr, tenv ); - } - - void Finder::postvisit( const ast::OffsetPackExpr * offsetPackExpr ) { - addCandidate( offsetPackExpr, tenv ); - } - - void Finder::postvisit( const ast::LogicalExpr * logicalExpr ) { - CandidateFinder finder1( context, tenv ); - finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() ); - if ( finder1.candidates.empty() ) return; - - CandidateFinder finder2( context, tenv ); - finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() ); - if ( finder2.candidates.empty() ) return; - - reason.code = NoMatch; - - for ( const CandidateRef & r1 : finder1.candidates ) { - for ( const CandidateRef & r2 : finder2.candidates ) { - ast::TypeEnvironment env{ r1->env }; - env.simpleCombine( r2->env ); - ast::OpenVarSet open{ r1->open }; - mergeOpenVars( open, r2->open ); - ast::AssertionSet need; - mergeAssertionSet( need, r1->need ); - mergeAssertionSet( need, r2->need ); - - addCandidate( - new ast::LogicalExpr{ - logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd }, - std::move( env ), std::move( open ), std::move( need ), r1->cost + r2->cost ); - } - } - } - - void Finder::postvisit( const ast::ConditionalExpr * conditionalExpr ) { - // candidates for condition - CandidateFinder finder1( context, tenv ); - finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() ); - if ( finder1.candidates.empty() ) return; - - // candidates for true result - CandidateFinder finder2( context, tenv ); - finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() ); - if ( finder2.candidates.empty() ) return; - - // candidates for false result - CandidateFinder finder3( context, tenv ); - finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() ); - if ( finder3.candidates.empty() ) return; - - reason.code = NoMatch; - - for ( const CandidateRef & r1 : finder1.candidates ) { - for ( const CandidateRef & r2 : finder2.candidates ) { - for ( const CandidateRef & r3 : finder3.candidates ) { - ast::TypeEnvironment env{ r1->env }; - env.simpleCombine( r2->env ); - env.simpleCombine( r3->env ); - ast::OpenVarSet open{ r1->open }; - mergeOpenVars( open, r2->open ); - mergeOpenVars( open, r3->open ); - ast::AssertionSet need; - mergeAssertionSet( need, r1->need ); - mergeAssertionSet( need, r2->need ); - mergeAssertionSet( need, r3->need ); - ast::AssertionSet have; - - // unify true and false results, then infer parameters to produce new - // candidates - ast::ptr< ast::Type > common; - if ( - unify( - r2->expr->result, r3->expr->result, env, need, have, open, - common ) - ) { - // generate typed expression - ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{ - conditionalExpr->location, r1->expr, r2->expr, r3->expr }; - newExpr->result = common ? common : r2->expr->result; - // convert both options to result type - Cost cost = r1->cost + r2->cost + r3->cost; - newExpr->arg2 = computeExpressionConversionCost( - newExpr->arg2, newExpr->result, symtab, env, cost ); - newExpr->arg3 = computeExpressionConversionCost( - newExpr->arg3, newExpr->result, symtab, env, cost ); - // output candidate - CandidateRef newCand = std::make_shared( - newExpr, std::move( env ), std::move( open ), std::move( need ), cost ); - inferParameters( newCand, candidates ); - } - } - } - } - } - - void Finder::postvisit( const ast::CommaExpr * commaExpr ) { - ast::TypeEnvironment env{ tenv }; - ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, context, env ); - - CandidateFinder finder2( context, env ); - finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() ); - - for ( const CandidateRef & r2 : finder2.candidates ) { - addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } ); - } - } - - void Finder::postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) { - addCandidate( ctorExpr, tenv ); - } - - void Finder::postvisit( const ast::ConstructorExpr * ctorExpr ) { - CandidateFinder finder( context, tenv ); - finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() ); - for ( CandidateRef & r : finder.candidates ) { - addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } ); - } - } - - void Finder::postvisit( const ast::RangeExpr * rangeExpr ) { - // resolve low and high, accept candidates where low and high types unify - CandidateFinder finder1( context, tenv ); - finder1.find( rangeExpr->low, ResolvMode::withAdjustment() ); - if ( finder1.candidates.empty() ) return; - - CandidateFinder finder2( context, tenv ); - finder2.find( rangeExpr->high, ResolvMode::withAdjustment() ); - if ( finder2.candidates.empty() ) return; - - reason.code = NoMatch; - - for ( const CandidateRef & r1 : finder1.candidates ) { - for ( const CandidateRef & r2 : finder2.candidates ) { - ast::TypeEnvironment env{ r1->env }; - env.simpleCombine( r2->env ); - ast::OpenVarSet open{ r1->open }; - mergeOpenVars( open, r2->open ); - ast::AssertionSet need; - mergeAssertionSet( need, r1->need ); - mergeAssertionSet( need, r2->need ); - ast::AssertionSet have; - - ast::ptr< ast::Type > common; - if ( - unify( - r1->expr->result, r2->expr->result, env, need, have, open, - common ) - ) { - // generate new expression - ast::RangeExpr * newExpr = - new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr }; - newExpr->result = common ? common : r1->expr->result; - // add candidate - CandidateRef newCand = std::make_shared( - newExpr, std::move( env ), std::move( open ), std::move( need ), - r1->cost + r2->cost ); - inferParameters( newCand, candidates ); - } - } - } - } - - void Finder::postvisit( const ast::UntypedTupleExpr * tupleExpr ) { - std::vector< CandidateFinder > subCandidates = - selfFinder.findSubExprs( tupleExpr->exprs ); - std::vector< CandidateList > possibilities; - combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) ); - - for ( const CandidateList & subs : possibilities ) { - std::vector< ast::ptr< ast::Expr > > exprs; - exprs.reserve( subs.size() ); - for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); } - - ast::TypeEnvironment env; - ast::OpenVarSet open; - ast::AssertionSet need; - for ( const CandidateRef & sub : subs ) { - env.simpleCombine( sub->env ); - mergeOpenVars( open, sub->open ); - mergeAssertionSet( need, sub->need ); - } - - addCandidate( - new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) }, - std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) ); - } - } - - void Finder::postvisit( const ast::TupleExpr * tupleExpr ) { - addCandidate( tupleExpr, tenv ); - } - - void Finder::postvisit( const ast::TupleIndexExpr * tupleExpr ) { - addCandidate( tupleExpr, tenv ); - } - - void Finder::postvisit( const ast::TupleAssignExpr * tupleExpr ) { - addCandidate( tupleExpr, tenv ); - } - - void Finder::postvisit( const ast::UniqueExpr * unqExpr ) { - CandidateFinder finder( context, tenv ); - finder.find( unqExpr->expr, ResolvMode::withAdjustment() ); - for ( CandidateRef & r : finder.candidates ) { - // ensure that the the id is passed on so that the expressions are "linked" - addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } ); - } - } - - void Finder::postvisit( const ast::StmtExpr * stmtExpr ) { - addCandidate( resolveStmtExpr( stmtExpr, context ), tenv ); - } - - void Finder::postvisit( const ast::UntypedInitExpr * initExpr ) { - // handle each option like a cast - CandidateList matches; - PRINT( - std::cerr << "untyped init expr: " << initExpr << std::endl; - ) - // O(n^2) checks of d-types with e-types - for ( const ast::InitAlternative & initAlt : initExpr->initAlts ) { - // calculate target type - const ast::Type * toType = resolveTypeof( initAlt.type, context ); - toType = adjustExprType( toType, tenv, symtab ); - // The call to find must occur inside this loop, otherwise polymorphic return - // types are not bound to the initialization type, since return type variables are - // only open for the duration of resolving the UntypedExpr. - CandidateFinder finder( context, tenv, toType ); - finder.find( initExpr->expr, ResolvMode::withAdjustment() ); - for ( CandidateRef & cand : finder.candidates ) { - if (reason.code == NotFound) reason.code = NoMatch; - - ast::TypeEnvironment env{ cand->env }; - ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have; - ast::OpenVarSet open{ cand->open }; - - PRINT( - std::cerr << " @ " << toType << " " << initAlt.designation << std::endl; - ) - - // It is possible that a cast can throw away some values in a multiply-valued - // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of - // the subexpression results that are cast directly. The candidate is invalid - // if it has fewer results than there are types to cast to. - int discardedValues = cand->expr->result->size() - toType->size(); - if ( discardedValues < 0 ) continue; - - // unification run for side-effects - bool canUnify = unify( toType, cand->expr->result, env, need, have, open ); - (void) canUnify; - Cost thisCost = computeConversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), - symtab, env ); - PRINT( - Cost legacyCost = castCost( cand->expr->result, toType, cand->expr->get_lvalue(), - symtab, env ); - std::cerr << "Considering initialization:"; - std::cerr << std::endl << " FROM: " << cand->expr->result << std::endl; - std::cerr << std::endl << " TO: " << toType << std::endl; - std::cerr << std::endl << " Unification " << (canUnify ? "succeeded" : "failed"); - std::cerr << std::endl << " Legacy cost " << legacyCost; - std::cerr << std::endl << " New cost " << thisCost; - std::cerr << std::endl; - ) - if ( thisCost != Cost::infinity ) { - // count one safe conversion for each value that is thrown away - thisCost.incSafe( discardedValues ); - CandidateRef newCand = std::make_shared( - new ast::InitExpr{ - initExpr->location, restructureCast( cand->expr, toType ), - initAlt.designation }, - std::move(env), std::move( open ), std::move( need ), cand->cost, thisCost ); - inferParameters( newCand, matches ); - } - } - } - - // select first on argument cost, then conversion cost - CandidateList minArgCost = findMinCost( matches ); - promoteCvtCost( minArgCost ); - candidates = findMinCost( minArgCost ); - } - - // size_t Finder::traceId = Stats::Heap::new_stacktrace_id("Finder"); - /// Prunes a list of candidates down to those that have the minimum conversion cost for a given - /// return type. Skips ambiguous candidates. - -} // anonymous namespace - -bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector & errors ) { - struct PruneStruct { - CandidateRef candidate; - bool ambiguous; - - PruneStruct() = default; - PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {} - }; - - // find lowest-cost candidate for each type - std::unordered_map< std::string, PruneStruct > selected; - // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found - std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;}); - for ( CandidateRef & candidate : candidates ) { - std::string mangleName; - { - ast::ptr< ast::Type > newType = candidate->expr->result; - assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get()); - candidate->env.apply( newType ); - mangleName = Mangle::mangle( newType ); - } - - auto found = selected.find( mangleName ); - if (found != selected.end() && found->second.candidate->cost < candidate->cost) { - PRINT( - std::cerr << "cost " << candidate->cost << " loses to " - << found->second.candidate->cost << std::endl; - ) - continue; - } - - // xxx - when do satisfyAssertions produce more than 1 result? - // this should only happen when initial result type contains - // unbound type parameters, then it should never be pruned by - // the previous step, since renameTyVars guarantees the mangled name - // is unique. - CandidateList satisfied; - bool needRecomputeKey = false; - if (candidate->need.empty()) { - satisfied.emplace_back(candidate); - } - else { - satisfyAssertions(candidate, context.symtab, satisfied, errors); - needRecomputeKey = true; - } - - for (auto & newCand : satisfied) { - // recomputes type key, if satisfyAssertions changed it - if (needRecomputeKey) - { - ast::ptr< ast::Type > newType = newCand->expr->result; - assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get()); - newCand->env.apply( newType ); - mangleName = Mangle::mangle( newType ); - } - auto found = selected.find( mangleName ); - if ( found != selected.end() ) { - if ( newCand->cost < found->second.candidate->cost ) { - PRINT( - std::cerr << "cost " << newCand->cost << " beats " - << found->second.candidate->cost << std::endl; - ) - - found->second = PruneStruct{ newCand }; - } else if ( newCand->cost == found->second.candidate->cost ) { - // if one of the candidates contains a deleted identifier, can pick the other, - // since deleted expressions should not be ambiguous if there is another option - // that is at least as good - if ( findDeletedExpr( newCand->expr ) ) { - // do nothing - PRINT( std::cerr << "candidate is deleted" << std::endl; ) - } else if ( findDeletedExpr( found->second.candidate->expr ) ) { - PRINT( std::cerr << "current is deleted" << std::endl; ) - found->second = PruneStruct{ newCand }; - } else { - PRINT( std::cerr << "marking ambiguous" << std::endl; ) - found->second.ambiguous = true; - } - } else { - // xxx - can satisfyAssertions increase the cost? - PRINT( - std::cerr << "cost " << newCand->cost << " loses to " - << found->second.candidate->cost << std::endl; - ) - } - } else { - selected.emplace_hint( found, mangleName, newCand ); - } - } - } - - // report unambiguous min-cost candidates - // CandidateList out; - for ( auto & target : selected ) { - if ( target.second.ambiguous ) continue; - - CandidateRef cand = target.second.candidate; - - ast::ptr< ast::Type > newResult = cand->expr->result; - cand->env.applyFree( newResult ); - cand->expr = ast::mutate_field( - cand->expr.get(), &ast::Expr::result, std::move( newResult ) ); - - out.emplace_back( cand ); - } - // if everything is lost in satisfyAssertions, report the error - return !selected.empty(); -} - -void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) { - // Find alternatives for expression - ast::Pass finder{ *this }; - expr->accept( finder ); - - if ( mode.failFast && candidates.empty() ) { - switch(finder.core.reason.code) { - case Finder::NotFound: - { SemanticError( expr, "No alternatives for expression " ); break; } - case Finder::NoMatch: - { SemanticError( expr, "Invalid application of existing declaration(s) in expression " ); break; } - case Finder::ArgsToFew: - case Finder::ArgsToMany: - case Finder::RetsToFew: - case Finder::RetsToMany: - case Finder::NoReason: - default: - { SemanticError( expr->location, "No reasonable alternatives for expression : reasons unkown" ); } - } - } - - /* - if ( mode.satisfyAssns || mode.prune ) { - // trim candidates to just those where the assertions are satisfiable - // - necessary pre-requisite to pruning - CandidateList satisfied; - std::vector< std::string > errors; - for ( CandidateRef & candidate : candidates ) { - satisfyAssertions( candidate, localSyms, satisfied, errors ); - } - - // fail early if none such - if ( mode.failFast && satisfied.empty() ) { - std::ostringstream stream; - stream << "No alternatives with satisfiable assertions for " << expr << "\n"; - for ( const auto& err : errors ) { - stream << err; - } - SemanticError( expr->location, stream.str() ); - } - - // reset candidates - candidates = move( satisfied ); - } - */ - - if ( mode.prune ) { - // trim candidates to single best one - PRINT( - std::cerr << "alternatives before prune:" << std::endl; - print( std::cerr, candidates ); - ) - - CandidateList pruned; - std::vector errors; - bool found = pruneCandidates( candidates, pruned, errors ); - - if ( mode.failFast && pruned.empty() ) { - std::ostringstream stream; - if (found) { - CandidateList winners = findMinCost( candidates ); - stream << "Cannot choose between " << winners.size() << " alternatives for " - "expression\n"; - ast::print( stream, expr ); - stream << " Alternatives are:\n"; - print( stream, winners, 1 ); - SemanticError( expr->location, stream.str() ); - } - else { - stream << "No alternatives with satisfiable assertions for " << expr << "\n"; - for ( const auto& err : errors ) { - stream << err; - } - SemanticError( expr->location, stream.str() ); - } - } - - auto oldsize = candidates.size(); - candidates = std::move( pruned ); - - PRINT( - std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; - ) - PRINT( - std::cerr << "there are " << candidates.size() << " alternatives after elimination" - << std::endl; - ) - } - - // adjust types after pruning so that types substituted by pruneAlternatives are correctly - // adjusted - if ( mode.adjust ) { - for ( CandidateRef & r : candidates ) { - r->expr = ast::mutate_field( - r->expr.get(), &ast::Expr::result, - adjustExprType( r->expr->result, r->env, context.symtab ) ); - } - } - - // Central location to handle gcc extension keyword, etc. for all expressions - for ( CandidateRef & r : candidates ) { - if ( r->expr->extension != expr->extension ) { - r->expr.get_and_mutate()->extension = expr->extension; - } - } -} - -std::vector< CandidateFinder > CandidateFinder::findSubExprs( - const std::vector< ast::ptr< ast::Expr > > & xs -) { - std::vector< CandidateFinder > out; - - for ( const auto & x : xs ) { - out.emplace_back( context, env ); - out.back().find( x, ResolvMode::withAdjustment() ); - - PRINT( - std::cerr << "findSubExprs" << std::endl; - print( std::cerr, out.back().candidates ); - ) - } - - return out; -} - const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) { if ( expr->result.as< ast::ReferenceType >() ) { @@ -1942,4 +65,7 @@ return expr; } + +/// Unique identifier for matching expression resolutions to their requesting expression +UniqueId globalResnSlot = 0; Cost computeConversionCost( @@ -1968,4 +94,1901 @@ } +namespace { + /// First index is which argument, second is which alternative, third is which exploded element + using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >; + + /// Returns a list of alternatives with the minimum cost in the given list + CandidateList findMinCost( const CandidateList & candidates ) { + CandidateList out; + Cost minCost = Cost::infinity; + for ( const CandidateRef & r : candidates ) { + if ( r->cost < minCost ) { + minCost = r->cost; + out.clear(); + out.emplace_back( r ); + } else if ( r->cost == minCost ) { + out.emplace_back( r ); + } + } + return out; + } + + /// Computes conversion cost for a given expression to a given type + const ast::Expr * computeExpressionConversionCost( + const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost + ) { + Cost convCost = computeConversionCost( + arg->result, paramType, arg->get_lvalue(), symtab, env ); + outCost += convCost; + + // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires + // conversion. Ignore poly cost for now, since this requires resolution of the cast to + // infer parameters and this does not currently work for the reason stated below + Cost tmpCost = convCost; + tmpCost.incPoly( -tmpCost.get_polyCost() ); + if ( tmpCost != Cost::zero ) { + ast::ptr< ast::Type > newType = paramType; + env.apply( newType ); + return new ast::CastExpr{ arg, newType }; + + // xxx - *should* be able to resolve this cast, but at the moment pointers are not + // castable to zero_t, but are implicitly convertible. This is clearly inconsistent, + // once this is fixed it should be possible to resolve the cast. + // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable, + // but it shouldn't be because this makes the conversion from DT* to DT* since + // commontype(zero_t, DT*) is DT*, rather than nothing + + // CandidateFinder finder{ symtab, env }; + // finder.find( arg, ResolvMode::withAdjustment() ); + // assertf( finder.candidates.size() > 0, + // "Somehow castable expression failed to find alternatives." ); + // assertf( finder.candidates.size() == 1, + // "Somehow got multiple alternatives for known cast expression." ); + // return finder.candidates.front()->expr; + } + + return arg; + } + + /// Computes conversion cost for a given candidate + Cost computeApplicationConversionCost( + CandidateRef cand, const ast::SymbolTable & symtab + ) { + auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >(); + auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); + auto function = pointer->base.strict_as< ast::FunctionType >(); + + Cost convCost = Cost::zero; + const auto & params = function->params; + auto param = params.begin(); + auto & args = appExpr->args; + + for ( unsigned i = 0; i < args.size(); ++i ) { + const ast::Type * argType = args[i]->result; + PRINT( + std::cerr << "arg expression:" << std::endl; + ast::print( std::cerr, args[i], 2 ); + std::cerr << "--- results are" << std::endl; + ast::print( std::cerr, argType, 2 ); + ) + + if ( param == params.end() ) { + if ( function->isVarArgs ) { + convCost.incUnsafe(); + PRINT( std::cerr << "end of params with varargs function: inc unsafe: " + << convCost << std::endl; ; ) + // convert reference-typed expressions into value-typed expressions + cand->expr = ast::mutate_field_index( + appExpr, &ast::ApplicationExpr::args, i, + referenceToRvalueConversion( args[i], convCost ) ); + continue; + } else return Cost::infinity; + } + + if ( auto def = args[i].as< ast::DefaultArgExpr >() ) { + // Default arguments should be free - don't include conversion cost. + // Unwrap them here because they are not relevant to the rest of the system + cand->expr = ast::mutate_field_index( + appExpr, &ast::ApplicationExpr::args, i, def->expr ); + ++param; + continue; + } + + // mark conversion cost and also specialization cost of param type + // const ast::Type * paramType = (*param)->get_type(); + cand->expr = ast::mutate_field_index( + appExpr, &ast::ApplicationExpr::args, i, + computeExpressionConversionCost( + args[i], *param, symtab, cand->env, convCost ) ); + convCost.decSpec( specCost( *param ) ); + ++param; // can't be in for-loop update because of the continue + } + + if ( param != params.end() ) return Cost::infinity; + + // specialization cost of return types can't be accounted for directly, it disables + // otherwise-identical calls, like this example based on auto-newline in the I/O lib: + // + // forall(otype OS) { + // void ?|?(OS&, int); // with newline + // OS& ?|?(OS&, int); // no newline, always chosen due to more specialization + // } + + // mark type variable and specialization cost of forall clause + convCost.incVar( function->forall.size() ); + convCost.decSpec( function->assertions.size() ); + + return convCost; + } + + void makeUnifiableVars( + const ast::FunctionType * type, ast::OpenVarSet & unifiableVars, + ast::AssertionSet & need + ) { + for ( auto & tyvar : type->forall ) { + unifiableVars[ *tyvar ] = ast::TypeData{ tyvar->base }; + } + for ( auto & assn : type->assertions ) { + need[ assn ].isUsed = true; + } + } + + /// Gets a default value from an initializer, nullptr if not present + const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) { + if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) { + if ( auto ce = si->value.as< ast::CastExpr >() ) { + return ce->arg.as< ast::ConstantExpr >(); + } else { + return si->value.as< ast::ConstantExpr >(); + } + } + return nullptr; + } + + /// State to iteratively build a match of parameter expressions to arguments + struct ArgPack { + std::size_t parent; ///< Index of parent pack + ast::ptr< ast::Expr > expr; ///< The argument stored here + Cost cost; ///< The cost of this argument + ast::TypeEnvironment env; ///< Environment for this pack + ast::AssertionSet need; ///< Assertions outstanding for this pack + ast::AssertionSet have; ///< Assertions found for this pack + ast::OpenVarSet open; ///< Open variables for this pack + unsigned nextArg; ///< Index of next argument in arguments list + unsigned tupleStart; ///< Number of tuples that start at this index + unsigned nextExpl; ///< Index of next exploded element + unsigned explAlt; ///< Index of alternative for nextExpl > 0 + + ArgPack() + : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ), + tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} + + ArgPack( + const ast::TypeEnvironment & env, const ast::AssertionSet & need, + const ast::AssertionSet & have, const ast::OpenVarSet & open ) + : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ), + open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} + + ArgPack( + std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env, + ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open, + unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero, + unsigned nextExpl = 0, unsigned explAlt = 0 ) + : parent(parent), expr( expr ), cost( cost ), env( std::move( env ) ), need( std::move( need ) ), + have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ), + nextExpl( nextExpl ), explAlt( explAlt ) {} + + ArgPack( + const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need, + ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added ) + : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( std::move( env ) ), + need( std::move( need ) ), have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ), + tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {} + + /// true if this pack is in the middle of an exploded argument + bool hasExpl() const { return nextExpl > 0; } + + /// Gets the list of exploded candidates for this pack + const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const { + return args[ nextArg-1 ][ explAlt ]; + } + + /// Ends a tuple expression, consolidating the appropriate args + void endTuple( const std::vector< ArgPack > & packs ) { + // add all expressions in tuple to list, summing cost + std::deque< const ast::Expr * > exprs; + const ArgPack * pack = this; + if ( expr ) { exprs.emplace_front( expr ); } + while ( pack->tupleStart == 0 ) { + pack = &packs[pack->parent]; + exprs.emplace_front( pack->expr ); + cost += pack->cost; + } + // reset pack to appropriate tuple + std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() ); + expr = new ast::TupleExpr{ expr->location, std::move( exprv ) }; + tupleStart = pack->tupleStart - 1; + parent = pack->parent; + } + }; + + /// Instantiates an argument to match a parameter, returns false if no matching results left + bool instantiateArgument( + const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args, + std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab, + unsigned nTuples = 0 + ) { + if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) { + // paramType is a TupleType -- group args into a TupleExpr + ++nTuples; + for ( const ast::Type * type : *tupleType ) { + // xxx - dropping initializer changes behaviour from previous, but seems correct + // ^^^ need to handle the case where a tuple has a default argument + if ( ! instantiateArgument( + type, nullptr, args, results, genStart, symtab, nTuples ) ) return false; + nTuples = 0; + } + // re-constitute tuples for final generation + for ( auto i = genStart; i < results.size(); ++i ) { + results[i].endTuple( results ); + } + return true; + } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) { + // paramType is a ttype, consumes all remaining arguments + + // completed tuples; will be spliced to end of results to finish + std::vector< ArgPack > finalResults{}; + + // iterate until all results completed + std::size_t genEnd; + ++nTuples; + do { + genEnd = results.size(); + + // add another argument to results + for ( std::size_t i = genStart; i < genEnd; ++i ) { + unsigned nextArg = results[i].nextArg; + + // use next element of exploded tuple if present + if ( results[i].hasExpl() ) { + const ExplodedArg & expl = results[i].getExpl( args ); + + unsigned nextExpl = results[i].nextExpl + 1; + if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } + + results.emplace_back( + i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ), + copy( results[i].need ), copy( results[i].have ), + copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl, + results[i].explAlt ); + + continue; + } + + // finish result when out of arguments + if ( nextArg >= args.size() ) { + ArgPack newResult{ + results[i].env, results[i].need, results[i].have, results[i].open }; + newResult.nextArg = nextArg; + const ast::Type * argType = nullptr; + + if ( nTuples > 0 || ! results[i].expr ) { + // first iteration or no expression to clone, + // push empty tuple expression + newResult.parent = i; + newResult.expr = new ast::TupleExpr{ CodeLocation{}, {} }; + argType = newResult.expr->result; + } else { + // clone result to collect tuple + newResult.parent = results[i].parent; + newResult.cost = results[i].cost; + newResult.tupleStart = results[i].tupleStart; + newResult.expr = results[i].expr; + argType = newResult.expr->result; + + if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) { + // the case where a ttype value is passed directly is special, + // e.g. for argument forwarding purposes + // xxx - what if passing multiple arguments, last of which is + // ttype? + // xxx - what would happen if unify was changed so that unifying + // tuple + // types flattened both before unifying lists? then pass in + // TupleType (ttype) below. + --newResult.tupleStart; + } else { + // collapse leftover arguments into tuple + newResult.endTuple( results ); + argType = newResult.expr->result; + } + } + + // check unification for ttype before adding to final + if ( + unify( + ttype, argType, newResult.env, newResult.need, newResult.have, + newResult.open ) + ) { + finalResults.emplace_back( std::move( newResult ) ); + } + + continue; + } + + // add each possible next argument + for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { + const ExplodedArg & expl = args[nextArg][j]; + + // fresh copies of parent parameters for this iteration + ast::TypeEnvironment env = results[i].env; + ast::OpenVarSet open = results[i].open; + + env.addActual( expl.env, open ); + + // skip empty tuple arguments by (nearly) cloning parent into next gen + if ( expl.exprs.empty() ) { + results.emplace_back( + results[i], std::move( env ), copy( results[i].need ), + copy( results[i].have ), std::move( open ), nextArg + 1, expl.cost ); + + continue; + } + + // add new result + results.emplace_back( + i, expl.exprs.front(), std::move( env ), copy( results[i].need ), + copy( results[i].have ), std::move( open ), nextArg + 1, nTuples, + expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); + } + } + + // reset for next round + genStart = genEnd; + nTuples = 0; + } while ( genEnd != results.size() ); + + // splice final results onto results + for ( std::size_t i = 0; i < finalResults.size(); ++i ) { + results.emplace_back( std::move( finalResults[i] ) ); + } + return ! finalResults.empty(); + } + + // iterate each current subresult + std::size_t genEnd = results.size(); + for ( std::size_t i = genStart; i < genEnd; ++i ) { + unsigned nextArg = results[i].nextArg; + + // use remainder of exploded tuple if present + if ( results[i].hasExpl() ) { + const ExplodedArg & expl = results[i].getExpl( args ); + const ast::Expr * expr = expl.exprs[ results[i].nextExpl ]; + + ast::TypeEnvironment env = results[i].env; + ast::AssertionSet need = results[i].need, have = results[i].have; + ast::OpenVarSet open = results[i].open; + + const ast::Type * argType = expr->result; + + PRINT( + std::cerr << "param type is "; + ast::print( std::cerr, paramType ); + std::cerr << std::endl << "arg type is "; + ast::print( std::cerr, argType ); + std::cerr << std::endl; + ) + + if ( unify( paramType, argType, env, need, have, open ) ) { + unsigned nextExpl = results[i].nextExpl + 1; + if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } + + results.emplace_back( + i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), nextArg, + nTuples, Cost::zero, nextExpl, results[i].explAlt ); + } + + continue; + } + + // use default initializers if out of arguments + if ( nextArg >= args.size() ) { + if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) { + ast::TypeEnvironment env = results[i].env; + ast::AssertionSet need = results[i].need, have = results[i].have; + ast::OpenVarSet open = results[i].open; + + if ( unify( paramType, cnst->result, env, need, have, open ) ) { + results.emplace_back( + i, new ast::DefaultArgExpr{ cnst->location, cnst }, std::move( env ), + std::move( need ), std::move( have ), std::move( open ), nextArg, nTuples ); + } + } + + continue; + } + + // Check each possible next argument + for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { + const ExplodedArg & expl = args[nextArg][j]; + + // fresh copies of parent parameters for this iteration + ast::TypeEnvironment env = results[i].env; + ast::AssertionSet need = results[i].need, have = results[i].have; + ast::OpenVarSet open = results[i].open; + + env.addActual( expl.env, open ); + + // skip empty tuple arguments by (nearly) cloning parent into next gen + if ( expl.exprs.empty() ) { + results.emplace_back( + results[i], std::move( env ), std::move( need ), std::move( have ), std::move( open ), + nextArg + 1, expl.cost ); + + continue; + } + + // consider only first exploded arg + const ast::Expr * expr = expl.exprs.front(); + const ast::Type * argType = expr->result; + + PRINT( + std::cerr << "param type is "; + ast::print( std::cerr, paramType ); + std::cerr << std::endl << "arg type is "; + ast::print( std::cerr, argType ); + std::cerr << std::endl; + ) + + // attempt to unify types + if ( unify( paramType, argType, env, need, have, open ) ) { + // add new result + results.emplace_back( + i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), + nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); + } + } + } + + // reset for next parameter + genStart = genEnd; + + return genEnd != results.size(); // were any new results added? + } + + /// Generate a cast expression from `arg` to `toType` + const ast::Expr * restructureCast( + ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast + ) { + if ( + arg->result->size() > 1 + && ! toType->isVoid() + && ! dynamic_cast< const ast::ReferenceType * >( toType ) + ) { + // Argument is a tuple and the target type is neither void nor a reference. Cast each + // member of the tuple to its corresponding target type, producing the tuple of those + // cast expressions. If there are more components of the tuple than components in the + // target type, then excess components do not come out in the result expression (but + // UniqueExpr ensures that the side effects will still be produced) + if ( Tuples::maybeImpureIgnoreUnique( arg ) ) { + // expressions which may contain side effects require a single unique instance of + // the expression + arg = new ast::UniqueExpr{ arg->location, arg }; + } + std::vector< ast::ptr< ast::Expr > > components; + for ( unsigned i = 0; i < toType->size(); ++i ) { + // cast each component + ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i }; + components.emplace_back( + restructureCast( idx, toType->getComponent( i ), isGenerated ) ); + } + return new ast::TupleExpr{ arg->location, std::move( components ) }; + } else { + // handle normally + return new ast::CastExpr{ arg->location, arg, toType, isGenerated }; + } + } + + /// Gets the name from an untyped member expression (must be NameExpr) + const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) { + if ( memberExpr->member.as< ast::ConstantExpr >() ) { + SemanticError( memberExpr, "Indexed access to struct fields unsupported: " ); + } + + return memberExpr->member.strict_as< ast::NameExpr >()->name; + } + + /// Actually visits expressions to find their candidate interpretations + class Finder final : public ast::WithShortCircuiting { + const ResolveContext & context; + const ast::SymbolTable & symtab; + public: + // static size_t traceId; + CandidateFinder & selfFinder; + CandidateList & candidates; + const ast::TypeEnvironment & tenv; + ast::ptr< ast::Type > & targetType; + + enum Errors { + NotFound, + NoMatch, + ArgsToFew, + ArgsToMany, + RetsToFew, + RetsToMany, + NoReason + }; + + struct { + Errors code = NotFound; + } reason; + + Finder( CandidateFinder & f ) + : context( f.context ), symtab( context.symtab ), selfFinder( f ), + candidates( f.candidates ), tenv( f.env ), targetType( f.targetType ) {} + + void previsit( const ast::Node * ) { visit_children = false; } + + /// Convenience to add candidate to list + template + void addCandidate( Args &&... args ) { + candidates.emplace_back( new Candidate{ std::forward( args )... } ); + reason.code = NoReason; + } + + void postvisit( const ast::ApplicationExpr * applicationExpr ) { + addCandidate( applicationExpr, tenv ); + } + + /// Set up candidate assertions for inference + void inferParameters( CandidateRef & newCand, CandidateList & out ) { + // Set need bindings for any unbound assertions + UniqueId crntResnSlot = 0; // matching ID for this expression's assertions + for ( auto & assn : newCand->need ) { + // skip already-matched assertions + if ( assn.second.resnSlot != 0 ) continue; + // assign slot for expression if needed + if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; } + // fix slot to assertion + assn.second.resnSlot = crntResnSlot; + } + // pair slot to expression + if ( crntResnSlot != 0 ) { + newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot ); + } + + // add to output list; assertion satisfaction will occur later + out.emplace_back( newCand ); + } + + /// Completes a function candidate with arguments located + void validateFunctionCandidate( + const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, + CandidateList & out + ) { + ast::ApplicationExpr * appExpr = + new ast::ApplicationExpr{ func->expr->location, func->expr }; + // sum cost and accumulate arguments + std::deque< const ast::Expr * > args; + Cost cost = func->cost; + const ArgPack * pack = &result; + while ( pack->expr ) { + args.emplace_front( pack->expr ); + cost += pack->cost; + pack = &results[pack->parent]; + } + std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() ); + appExpr->args = std::move( vargs ); + // build and validate new candidate + auto newCand = + std::make_shared( appExpr, result.env, result.open, result.need, cost ); + PRINT( + std::cerr << "instantiate function success: " << appExpr << std::endl; + std::cerr << "need assertions:" << std::endl; + ast::print( std::cerr, result.need, 2 ); + ) + inferParameters( newCand, out ); + } + + /// Builds a list of candidates for a function, storing them in out + void makeFunctionCandidates( + const CandidateRef & func, const ast::FunctionType * funcType, + const ExplodedArgs_new & args, CandidateList & out + ) { + ast::OpenVarSet funcOpen; + ast::AssertionSet funcNeed, funcHave; + ast::TypeEnvironment funcEnv{ func->env }; + makeUnifiableVars( funcType, funcOpen, funcNeed ); + // add all type variables as open variables now so that those not used in the + // parameter list are still considered open + funcEnv.add( funcType->forall ); + + if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) { + // attempt to narrow based on expected target type + const ast::Type * returnType = funcType->returns.front(); + if ( selfFinder.strictMode ) { + if ( ! unifyExact( + returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, noWiden() ) // xxx - is no widening correct? + ) { + // unification failed, do not pursue this candidate + return; + } + } + else { + if ( ! unify( + returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen ) + ) { + // unification failed, do not pursue this candidate + return; + } + } + } + + // iteratively build matches, one parameter at a time + std::vector< ArgPack > results; + results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen ); + std::size_t genStart = 0; + + // xxx - how to handle default arg after change to ftype representation? + if (const ast::VariableExpr * varExpr = func->expr.as()) { + if (const ast::FunctionDecl * funcDecl = varExpr->var.as()) { + // function may have default args only if directly calling by name + // must use types on candidate however, due to RenameVars substitution + auto nParams = funcType->params.size(); + + for (size_t i=0; iparams[i].strict_as(); + if (!instantiateArgument( + funcType->params[i], obj->init, args, results, genStart, symtab)) return; + } + goto endMatch; + } + } + for ( const auto & param : funcType->params ) { + // Try adding the arguments corresponding to the current parameter to the existing + // matches + // no default args for indirect calls + if ( ! instantiateArgument( + param, nullptr, args, results, genStart, symtab ) ) return; + } + + endMatch: + if ( funcType->isVarArgs ) { + // append any unused arguments to vararg pack + std::size_t genEnd; + do { + genEnd = results.size(); + + // iterate results + for ( std::size_t i = genStart; i < genEnd; ++i ) { + unsigned nextArg = results[i].nextArg; + + // use remainder of exploded tuple if present + if ( results[i].hasExpl() ) { + const ExplodedArg & expl = results[i].getExpl( args ); + + unsigned nextExpl = results[i].nextExpl + 1; + if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } + + results.emplace_back( + i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ), + copy( results[i].need ), copy( results[i].have ), + copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl, + results[i].explAlt ); + + continue; + } + + // finish result when out of arguments + if ( nextArg >= args.size() ) { + validateFunctionCandidate( func, results[i], results, out ); + + continue; + } + + // add each possible next argument + for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { + const ExplodedArg & expl = args[nextArg][j]; + + // fresh copies of parent parameters for this iteration + ast::TypeEnvironment env = results[i].env; + ast::OpenVarSet open = results[i].open; + + env.addActual( expl.env, open ); + + // skip empty tuple arguments by (nearly) cloning parent into next gen + if ( expl.exprs.empty() ) { + results.emplace_back( + results[i], std::move( env ), copy( results[i].need ), + copy( results[i].have ), std::move( open ), nextArg + 1, + expl.cost ); + + continue; + } + + // add new result + results.emplace_back( + i, expl.exprs.front(), std::move( env ), copy( results[i].need ), + copy( results[i].have ), std::move( open ), nextArg + 1, 0, expl.cost, + expl.exprs.size() == 1 ? 0 : 1, j ); + } + } + + genStart = genEnd; + } while( genEnd != results.size() ); + } else { + // filter out the results that don't use all the arguments + for ( std::size_t i = genStart; i < results.size(); ++i ) { + ArgPack & result = results[i]; + if ( ! result.hasExpl() && result.nextArg >= args.size() ) { + validateFunctionCandidate( func, result, results, out ); + } + } + } + } + + /// Adds implicit struct-conversions to the alternative list + void addAnonConversions( const CandidateRef & cand ) { + // adds anonymous member interpretations whenever an aggregate value type is seen. + // it's okay for the aggregate expression to have reference type -- cast it to the + // base type to treat the aggregate as the referenced value + ast::ptr< ast::Expr > aggrExpr( cand->expr ); + ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result; + cand->env.apply( aggrType ); + + if ( aggrType.as< ast::ReferenceType >() ) { + aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() }; + } + + if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) { + addAggMembers( structInst, aggrExpr, *cand, Cost::unsafe, "" ); + } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) { + addAggMembers( unionInst, aggrExpr, *cand, Cost::unsafe, "" ); + } + } + + /// Adds aggregate member interpretations + void addAggMembers( + const ast::BaseInstType * aggrInst, const ast::Expr * expr, + const Candidate & cand, const Cost & addedCost, const std::string & name + ) { + for ( const ast::Decl * decl : aggrInst->lookup( name ) ) { + auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl ); + CandidateRef newCand = std::make_shared( + cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost ); + // add anonymous member interpretations whenever an aggregate value type is seen + // as a member expression + addAnonConversions( newCand ); + candidates.emplace_back( std::move( newCand ) ); + } + } + + /// Adds tuple member interpretations + void addTupleMembers( + const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, + const Cost & addedCost, const ast::Expr * member + ) { + if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) { + // get the value of the constant expression as an int, must be between 0 and the + // length of the tuple to have meaning + long long val = constantExpr->intValue(); + if ( val >= 0 && (unsigned long long)val < tupleType->size() ) { + addCandidate( + cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val }, + addedCost ); + } + } + } + + void postvisit( const ast::UntypedExpr * untypedExpr ) { + std::vector< CandidateFinder > argCandidates = + selfFinder.findSubExprs( untypedExpr->args ); + + // take care of possible tuple assignments + // if not tuple assignment, handled as normal function call + Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates ); + + CandidateFinder funcFinder( context, tenv ); + if (auto nameExpr = untypedExpr->func.as()) { + auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name); + if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) { + assertf(!argCandidates.empty(), "special function call without argument"); + for (auto & firstArgCand: argCandidates[0]) { + ast::ptr argType = firstArgCand->expr->result; + firstArgCand->env.apply(argType); + // strip references + // xxx - is this correct? + while (argType.as()) argType = argType.as()->base; + + // convert 1-tuple to plain type + if (auto tuple = argType.as()) { + if (tuple->size() == 1) { + argType = tuple->types[0]; + } + } + + // if argType is an unbound type parameter, all special functions need to be searched. + if (isUnboundType(argType)) { + funcFinder.otypeKeys.clear(); + break; + } + + if (argType.as()) funcFinder.otypeKeys.insert(Mangle::Encoding::pointer); + // else if (const ast::EnumInstType * enumInst = argType.as()) { + // const ast::EnumDecl * enumDecl = enumInst->base; // Here + // if ( const ast::Type* enumType = enumDecl->base ) { + // // instance of enum (T) is a instance of type (T) + // funcFinder.otypeKeys.insert(Mangle::mangle(enumType, Mangle::NoGenericParams | Mangle::Type)); + // } else { + // // instance of an untyped enum is techically int + // funcFinder.otypeKeys.insert(Mangle::mangle(enumDecl, Mangle::NoGenericParams | Mangle::Type)); + // } + // } + else funcFinder.otypeKeys.insert(Mangle::mangle(argType, Mangle::NoGenericParams | Mangle::Type)); + } + } + } + // if candidates are already produced, do not fail + // xxx - is it possible that handleTupleAssignment and main finder both produce candidates? + // this means there exists ctor/assign functions with a tuple as first parameter. + ResolvMode mode = { + true, // adjust + !untypedExpr->func.as(), // prune if not calling by name + selfFinder.candidates.empty() // failfast if other options are not found + }; + funcFinder.find( untypedExpr->func, mode ); + // short-circuit if no candidates + // if ( funcFinder.candidates.empty() ) return; + + reason.code = NoMatch; + + // find function operators + ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" }; // ??? why not ?{} + CandidateFinder opFinder( context, tenv ); + // okay if there aren't any function operations + opFinder.find( opExpr, ResolvMode::withoutFailFast() ); + PRINT( + std::cerr << "known function ops:" << std::endl; + print( std::cerr, opFinder.candidates, 1 ); + ) + + // pre-explode arguments + ExplodedArgs_new argExpansions; + for ( const CandidateFinder & args : argCandidates ) { + argExpansions.emplace_back(); + auto & argE = argExpansions.back(); + for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); } + } + + // Find function matches + CandidateList found; + SemanticErrorException errors; + for ( CandidateRef & func : funcFinder ) { + try { + PRINT( + std::cerr << "working on alternative:" << std::endl; + print( std::cerr, *func, 2 ); + ) + + // check if the type is a pointer to function + const ast::Type * funcResult = func->expr->result->stripReferences(); + if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) { + if ( auto function = pointer->base.as< ast::FunctionType >() ) { + // if (!selfFinder.allowVoid && function->returns.empty()) continue; + CandidateRef newFunc{ new Candidate{ *func } }; + newFunc->expr = + referenceToRvalueConversion( newFunc->expr, newFunc->cost ); + makeFunctionCandidates( newFunc, function, argExpansions, found ); + } + } else if ( + auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) + ) { + if ( const ast::EqvClass * clz = func->env.lookup( *inst ) ) { + if ( auto function = clz->bound.as< ast::FunctionType >() ) { + CandidateRef newFunc{ new Candidate{ *func } }; + newFunc->expr = + referenceToRvalueConversion( newFunc->expr, newFunc->cost ); + makeFunctionCandidates( newFunc, function, argExpansions, found ); + } + } + } + } catch ( SemanticErrorException & e ) { errors.append( e ); } + } + + // Find matches on function operators `?()` + if ( ! opFinder.candidates.empty() ) { + // add exploded function alternatives to front of argument list + std::vector< ExplodedArg > funcE; + funcE.reserve( funcFinder.candidates.size() ); + for ( const CandidateRef & func : funcFinder ) { + funcE.emplace_back( *func, symtab ); + } + argExpansions.emplace_front( std::move( funcE ) ); + + for ( const CandidateRef & op : opFinder ) { + try { + // check if type is pointer-to-function + const ast::Type * opResult = op->expr->result->stripReferences(); + if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) { + if ( auto function = pointer->base.as< ast::FunctionType >() ) { + CandidateRef newOp{ new Candidate{ *op} }; + newOp->expr = + referenceToRvalueConversion( newOp->expr, newOp->cost ); + makeFunctionCandidates( newOp, function, argExpansions, found ); + } + } + } catch ( SemanticErrorException & e ) { errors.append( e ); } + } + } + + // Implement SFINAE; resolution errors are only errors if there aren't any non-error + // candidates + if ( found.empty() && ! errors.isEmpty() ) { throw errors; } + + // only keep the best matching intrinsic result to match C semantics (no unexpected narrowing/widening) + // TODO: keep one for each set of argument candidates? + Cost intrinsicCost = Cost::infinity; + CandidateList intrinsicResult; + + // Compute conversion costs + for ( CandidateRef & withFunc : found ) { + Cost cvtCost = computeApplicationConversionCost( withFunc, symtab ); + + PRINT( + auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >(); + auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); + auto function = pointer->base.strict_as< ast::FunctionType >(); + + std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl; + std::cerr << "parameters are:" << std::endl; + ast::printAll( std::cerr, function->params, 2 ); + std::cerr << "arguments are:" << std::endl; + ast::printAll( std::cerr, appExpr->args, 2 ); + std::cerr << "bindings are:" << std::endl; + ast::print( std::cerr, withFunc->env, 2 ); + std::cerr << "cost is: " << withFunc->cost << std::endl; + std::cerr << "cost of conversion is:" << cvtCost << std::endl; + ) + + if ( cvtCost != Cost::infinity ) { + withFunc->cvtCost = cvtCost; + withFunc->cost += cvtCost; + auto func = withFunc->expr.strict_as()->func.as(); + if (func && func->var->linkage == ast::Linkage::Intrinsic) { + if (withFunc->cost < intrinsicCost) { + intrinsicResult.clear(); + intrinsicCost = withFunc->cost; + } + if (withFunc->cost == intrinsicCost) { + intrinsicResult.emplace_back(std::move(withFunc)); + } + } + else { + candidates.emplace_back( std::move( withFunc ) ); + } + } + } + spliceBegin( candidates, intrinsicResult ); + found = std::move( candidates ); + + // use a new list so that candidates are not examined by addAnonConversions twice + // CandidateList winners = findMinCost( found ); + // promoteCvtCost( winners ); + + // function may return a struct/union value, in which case we need to add candidates + // for implicit conversions to each of the anonymous members, which must happen after + // `findMinCost`, since anon conversions are never the cheapest + for ( const CandidateRef & c : found ) { + addAnonConversions( c ); + } + // would this be too slow when we don't check cost anymore? + spliceBegin( candidates, found ); + + if ( candidates.empty() && targetType && ! targetType->isVoid() && !selfFinder.strictMode ) { + // If resolution is unsuccessful with a target type, try again without, since it + // will sometimes succeed when it wouldn't with a target type binding. + // For example: + // forall( otype T ) T & ?[]( T *, ptrdiff_t ); + // const char * x = "hello world"; + // unsigned char ch = x[0]; + // Fails with simple return type binding (xxx -- check this!) as follows: + // * T is bound to unsigned char + // * (x: const char *) is unified with unsigned char *, which fails + // xxx -- fix this better + targetType = nullptr; + postvisit( untypedExpr ); + } + } + + /// true if expression is an lvalue + static bool isLvalue( const ast::Expr * x ) { + return x->result && ( x->get_lvalue() || x->result.as< ast::ReferenceType >() ); + } + + void postvisit( const ast::AddressExpr * addressExpr ) { + CandidateFinder finder( context, tenv ); + finder.find( addressExpr->arg ); + + if( finder.candidates.empty() ) return; + + reason.code = NoMatch; + + for ( CandidateRef & r : finder.candidates ) { + if ( ! isLvalue( r->expr ) ) continue; + addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } ); + } + } + + void postvisit( const ast::LabelAddressExpr * labelExpr ) { + addCandidate( labelExpr, tenv ); + } + + void postvisit( const ast::CastExpr * castExpr ) { + ast::ptr< ast::Type > toType = castExpr->result; + assert( toType ); + toType = resolveTypeof( toType, context ); + toType = adjustExprType( toType, tenv, symtab ); + + CandidateFinder finder( context, tenv, toType ); + if (toType->isVoid()) { + finder.allowVoid = true; + } + if ( castExpr->kind == ast::CastExpr::Return ) { + finder.strictMode = true; + finder.find( castExpr->arg, ResolvMode::withAdjustment() ); + + // return casts are eliminated (merely selecting an overload, no actual operation) + candidates = std::move(finder.candidates); + } + finder.find( castExpr->arg, ResolvMode::withAdjustment() ); + + if( !finder.candidates.empty() ) reason.code = NoMatch; + + CandidateList matches; + Cost minExprCost = Cost::infinity; + Cost minCastCost = Cost::infinity; + for ( CandidateRef & cand : finder.candidates ) { + ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have; + ast::OpenVarSet open( cand->open ); + + cand->env.extractOpenVars( open ); + + // It is possible that a cast can throw away some values in a multiply-valued + // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the + // subexpression results that are cast directly. The candidate is invalid if it + // has fewer results than there are types to cast to. + int discardedValues = cand->expr->result->size() - toType->size(); + if ( discardedValues < 0 ) continue; + + // unification run for side-effects + unify( toType, cand->expr->result, cand->env, need, have, open ); + Cost thisCost = + (castExpr->isGenerated == ast::GeneratedFlag::GeneratedCast) + ? conversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env ) + : castCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env ); + + PRINT( + std::cerr << "working on cast with result: " << toType << std::endl; + std::cerr << "and expr type: " << cand->expr->result << std::endl; + std::cerr << "env: " << cand->env << std::endl; + ) + if ( thisCost != Cost::infinity ) { + PRINT( + std::cerr << "has finite cost." << std::endl; + ) + // count one safe conversion for each value that is thrown away + thisCost.incSafe( discardedValues ); + // select first on argument cost, then conversion cost + if (cand->cost < minExprCost || cand->cost == minExprCost && thisCost < minCastCost) { + minExprCost = cand->cost; + minCastCost = thisCost; + matches.clear(); + + + } + // ambiguous case, still output candidates to print in error message + if (cand->cost == minExprCost && thisCost == minCastCost) { + CandidateRef newCand = std::make_shared( + restructureCast( cand->expr, toType, castExpr->isGenerated ), + copy( cand->env ), std::move( open ), std::move( need ), cand->cost + thisCost); + // currently assertions are always resolved immediately so this should have no effect. + // if this somehow changes in the future (e.g. delayed by indeterminate return type) + // we may need to revisit the logic. + inferParameters( newCand, matches ); + } + // else skip, better alternatives found + + } + } + candidates = std::move(matches); + + //CandidateList minArgCost = findMinCost( matches ); + //promoteCvtCost( minArgCost ); + //candidates = findMinCost( minArgCost ); + } + + void postvisit( const ast::VirtualCastExpr * castExpr ) { + assertf( castExpr->result, "Implicit virtual cast targets not yet supported." ); + CandidateFinder finder( context, tenv ); + // don't prune here, all alternatives guaranteed to have same type + finder.find( castExpr->arg, ResolvMode::withoutPrune() ); + for ( CandidateRef & r : finder.candidates ) { + addCandidate( + *r, + new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } ); + } + } + + void postvisit( const ast::KeywordCastExpr * castExpr ) { + const auto & loc = castExpr->location; + assertf( castExpr->result, "Cast target should have been set in Validate." ); + auto ref = castExpr->result.strict_as(); + auto inst = ref->base.strict_as(); + auto target = inst->base.get(); + + CandidateFinder finder( context, tenv ); + + auto pick_alternatives = [target, this](CandidateList & found, bool expect_ref) { + for(auto & cand : found) { + const ast::Type * expr = cand->expr->result.get(); + if(expect_ref) { + auto res = dynamic_cast(expr); + if(!res) { continue; } + expr = res->base.get(); + } + + if(auto insttype = dynamic_cast(expr)) { + auto td = cand->env.lookup(*insttype); + if(!td) { continue; } + expr = td->bound.get(); + } + + if(auto base = dynamic_cast(expr)) { + if(base->base == target) { + candidates.push_back( std::move(cand) ); + reason.code = NoReason; + } + } + } + }; + + try { + // Attempt 1 : turn (thread&)X into (thread$&)X.__thrd + // Clone is purely for memory management + std::unique_ptr tech1 { new ast::UntypedMemberExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.field), castExpr->arg) }; + + // don't prune here, since it's guaranteed all alternatives will have the same type + finder.find( tech1.get(), ResolvMode::withoutPrune() ); + pick_alternatives(finder.candidates, false); + + return; + } catch(SemanticErrorException & ) {} + + // Fallback : turn (thread&)X into (thread$&)get_thread(X) + std::unique_ptr fallback { ast::UntypedExpr::createDeref(loc, new ast::UntypedExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.getter), { castExpr->arg })) }; + // don't prune here, since it's guaranteed all alternatives will have the same type + finder.find( fallback.get(), ResolvMode::withoutPrune() ); + + pick_alternatives(finder.candidates, true); + + // Whatever happens here, we have no more fallbacks + } + + void postvisit( const ast::UntypedMemberExpr * memberExpr ) { + CandidateFinder aggFinder( context, tenv ); + aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() ); + for ( CandidateRef & agg : aggFinder.candidates ) { + // it's okay for the aggregate expression to have reference type -- cast it to the + // base type to treat the aggregate as the referenced value + Cost addedCost = Cost::zero; + agg->expr = referenceToRvalueConversion( agg->expr, addedCost ); + + // find member of the given type + if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) { + addAggMembers( + structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); + } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) { + addAggMembers( + unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); + } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) { + addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member ); + } + } + } + + void postvisit( const ast::MemberExpr * memberExpr ) { + addCandidate( memberExpr, tenv ); + } + + void postvisit( const ast::NameExpr * nameExpr ) { + std::vector< ast::SymbolTable::IdData > declList; + if (!selfFinder.otypeKeys.empty()) { + auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name); + assertf(kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS, "special lookup with non-special target: %s", nameExpr->name.c_str()); + + for (auto & otypeKey: selfFinder.otypeKeys) { + auto result = symtab.specialLookupId(kind, otypeKey); + declList.insert(declList.end(), std::make_move_iterator(result.begin()), std::make_move_iterator(result.end())); + } + } + else { + declList = symtab.lookupId( nameExpr->name ); + } + PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; ) + + if( declList.empty() ) return; + + reason.code = NoMatch; + + for ( auto & data : declList ) { + Cost cost = Cost::zero; + ast::Expr * newExpr = data.combine( nameExpr->location, cost ); + + CandidateRef newCand = std::make_shared( + newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, cost ); + + if (newCand->expr->env) { + newCand->env.add(*newCand->expr->env); + auto mutExpr = newCand->expr.get_and_mutate(); + mutExpr->env = nullptr; + newCand->expr = mutExpr; + } + + PRINT( + std::cerr << "decl is "; + ast::print( std::cerr, data.id ); + std::cerr << std::endl; + std::cerr << "newExpr is "; + ast::print( std::cerr, newExpr ); + std::cerr << std::endl; + ) + newCand->expr = ast::mutate_field( + newCand->expr.get(), &ast::Expr::result, + renameTyVars( newCand->expr->result ) ); + // add anonymous member interpretations whenever an aggregate value type is seen + // as a name expression + addAnonConversions( newCand ); + candidates.emplace_back( std::move( newCand ) ); + } + } + + void postvisit( const ast::VariableExpr * variableExpr ) { + // not sufficient to just pass `variableExpr` here, type might have changed since + // creation + addCandidate( + new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv ); + } + + void postvisit( const ast::ConstantExpr * constantExpr ) { + addCandidate( constantExpr, tenv ); + } + + void postvisit( const ast::SizeofExpr * sizeofExpr ) { + if ( sizeofExpr->type ) { + addCandidate( + new ast::SizeofExpr{ + sizeofExpr->location, resolveTypeof( sizeofExpr->type, context ) }, + tenv ); + } else { + // find all candidates for the argument to sizeof + CandidateFinder finder( context, tenv ); + finder.find( sizeofExpr->expr ); + // find the lowest-cost candidate, otherwise ambiguous + CandidateList winners = findMinCost( finder.candidates ); + if ( winners.size() != 1 ) { + SemanticError( + sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " ); + } + // return the lowest-cost candidate + CandidateRef & choice = winners.front(); + choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); + choice->cost = Cost::zero; + addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } ); + } + } + + void postvisit( const ast::AlignofExpr * alignofExpr ) { + if ( alignofExpr->type ) { + addCandidate( + new ast::AlignofExpr{ + alignofExpr->location, resolveTypeof( alignofExpr->type, context ) }, + tenv ); + } else { + // find all candidates for the argument to alignof + CandidateFinder finder( context, tenv ); + finder.find( alignofExpr->expr ); + // find the lowest-cost candidate, otherwise ambiguous + CandidateList winners = findMinCost( finder.candidates ); + if ( winners.size() != 1 ) { + SemanticError( + alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " ); + } + // return the lowest-cost candidate + CandidateRef & choice = winners.front(); + choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); + choice->cost = Cost::zero; + addCandidate( + *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } ); + } + } + + void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) { + const ast::BaseInstType * aggInst; + if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ; + else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ; + else return; + + for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) { + auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member ); + addCandidate( + new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv ); + } + } + + void postvisit( const ast::OffsetofExpr * offsetofExpr ) { + addCandidate( offsetofExpr, tenv ); + } + + void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) { + addCandidate( offsetPackExpr, tenv ); + } + + void postvisit( const ast::LogicalExpr * logicalExpr ) { + CandidateFinder finder1( context, tenv ); + finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() ); + if ( finder1.candidates.empty() ) return; + + CandidateFinder finder2( context, tenv ); + finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() ); + if ( finder2.candidates.empty() ) return; + + reason.code = NoMatch; + + for ( const CandidateRef & r1 : finder1.candidates ) { + for ( const CandidateRef & r2 : finder2.candidates ) { + ast::TypeEnvironment env{ r1->env }; + env.simpleCombine( r2->env ); + ast::OpenVarSet open{ r1->open }; + mergeOpenVars( open, r2->open ); + ast::AssertionSet need; + mergeAssertionSet( need, r1->need ); + mergeAssertionSet( need, r2->need ); + + addCandidate( + new ast::LogicalExpr{ + logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd }, + std::move( env ), std::move( open ), std::move( need ), r1->cost + r2->cost ); + } + } + } + + void postvisit( const ast::ConditionalExpr * conditionalExpr ) { + // candidates for condition + CandidateFinder finder1( context, tenv ); + finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() ); + if ( finder1.candidates.empty() ) return; + + // candidates for true result + CandidateFinder finder2( context, tenv ); + finder2.allowVoid = true; + finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() ); + if ( finder2.candidates.empty() ) return; + + // candidates for false result + CandidateFinder finder3( context, tenv ); + finder3.allowVoid = true; + finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() ); + if ( finder3.candidates.empty() ) return; + + reason.code = NoMatch; + + for ( const CandidateRef & r1 : finder1.candidates ) { + for ( const CandidateRef & r2 : finder2.candidates ) { + for ( const CandidateRef & r3 : finder3.candidates ) { + ast::TypeEnvironment env{ r1->env }; + env.simpleCombine( r2->env ); + env.simpleCombine( r3->env ); + ast::OpenVarSet open{ r1->open }; + mergeOpenVars( open, r2->open ); + mergeOpenVars( open, r3->open ); + ast::AssertionSet need; + mergeAssertionSet( need, r1->need ); + mergeAssertionSet( need, r2->need ); + mergeAssertionSet( need, r3->need ); + ast::AssertionSet have; + + // unify true and false results, then infer parameters to produce new + // candidates + ast::ptr< ast::Type > common; + if ( + unify( + r2->expr->result, r3->expr->result, env, need, have, open, + common ) + ) { + // generate typed expression + ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{ + conditionalExpr->location, r1->expr, r2->expr, r3->expr }; + newExpr->result = common ? common : r2->expr->result; + // convert both options to result type + Cost cost = r1->cost + r2->cost + r3->cost; + newExpr->arg2 = computeExpressionConversionCost( + newExpr->arg2, newExpr->result, symtab, env, cost ); + newExpr->arg3 = computeExpressionConversionCost( + newExpr->arg3, newExpr->result, symtab, env, cost ); + // output candidate + CandidateRef newCand = std::make_shared( + newExpr, std::move( env ), std::move( open ), std::move( need ), cost ); + inferParameters( newCand, candidates ); + } + } + } + } + } + + void postvisit( const ast::CommaExpr * commaExpr ) { + ast::TypeEnvironment env{ tenv }; + ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, context, env ); + + CandidateFinder finder2( context, env ); + finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() ); + + for ( const CandidateRef & r2 : finder2.candidates ) { + addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } ); + } + } + + void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) { + addCandidate( ctorExpr, tenv ); + } + + void postvisit( const ast::ConstructorExpr * ctorExpr ) { + CandidateFinder finder( context, tenv ); + finder.allowVoid = true; + finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() ); + for ( CandidateRef & r : finder.candidates ) { + addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } ); + } + } + + void postvisit( const ast::RangeExpr * rangeExpr ) { + // resolve low and high, accept candidates where low and high types unify + CandidateFinder finder1( context, tenv ); + finder1.find( rangeExpr->low, ResolvMode::withAdjustment() ); + if ( finder1.candidates.empty() ) return; + + CandidateFinder finder2( context, tenv ); + finder2.find( rangeExpr->high, ResolvMode::withAdjustment() ); + if ( finder2.candidates.empty() ) return; + + reason.code = NoMatch; + + for ( const CandidateRef & r1 : finder1.candidates ) { + for ( const CandidateRef & r2 : finder2.candidates ) { + ast::TypeEnvironment env{ r1->env }; + env.simpleCombine( r2->env ); + ast::OpenVarSet open{ r1->open }; + mergeOpenVars( open, r2->open ); + ast::AssertionSet need; + mergeAssertionSet( need, r1->need ); + mergeAssertionSet( need, r2->need ); + ast::AssertionSet have; + + ast::ptr< ast::Type > common; + if ( + unify( + r1->expr->result, r2->expr->result, env, need, have, open, + common ) + ) { + // generate new expression + ast::RangeExpr * newExpr = + new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr }; + newExpr->result = common ? common : r1->expr->result; + // add candidate + CandidateRef newCand = std::make_shared( + newExpr, std::move( env ), std::move( open ), std::move( need ), + r1->cost + r2->cost ); + inferParameters( newCand, candidates ); + } + } + } + } + + void postvisit( const ast::UntypedTupleExpr * tupleExpr ) { + std::vector< CandidateFinder > subCandidates = + selfFinder.findSubExprs( tupleExpr->exprs ); + std::vector< CandidateList > possibilities; + combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) ); + + for ( const CandidateList & subs : possibilities ) { + std::vector< ast::ptr< ast::Expr > > exprs; + exprs.reserve( subs.size() ); + for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); } + + ast::TypeEnvironment env; + ast::OpenVarSet open; + ast::AssertionSet need; + for ( const CandidateRef & sub : subs ) { + env.simpleCombine( sub->env ); + mergeOpenVars( open, sub->open ); + mergeAssertionSet( need, sub->need ); + } + + addCandidate( + new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) }, + std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) ); + } + } + + void postvisit( const ast::TupleExpr * tupleExpr ) { + addCandidate( tupleExpr, tenv ); + } + + void postvisit( const ast::TupleIndexExpr * tupleExpr ) { + addCandidate( tupleExpr, tenv ); + } + + void postvisit( const ast::TupleAssignExpr * tupleExpr ) { + addCandidate( tupleExpr, tenv ); + } + + void postvisit( const ast::UniqueExpr * unqExpr ) { + CandidateFinder finder( context, tenv ); + finder.find( unqExpr->expr, ResolvMode::withAdjustment() ); + for ( CandidateRef & r : finder.candidates ) { + // ensure that the the id is passed on so that the expressions are "linked" + addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } ); + } + } + + void postvisit( const ast::StmtExpr * stmtExpr ) { + addCandidate( resolveStmtExpr( stmtExpr, context ), tenv ); + } + + void postvisit( const ast::UntypedInitExpr * initExpr ) { + // handle each option like a cast + CandidateList matches; + PRINT( + std::cerr << "untyped init expr: " << initExpr << std::endl; + ) + // O(n^2) checks of d-types with e-types + for ( const ast::InitAlternative & initAlt : initExpr->initAlts ) { + // calculate target type + const ast::Type * toType = resolveTypeof( initAlt.type, context ); + toType = adjustExprType( toType, tenv, symtab ); + // The call to find must occur inside this loop, otherwise polymorphic return + // types are not bound to the initialization type, since return type variables are + // only open for the duration of resolving the UntypedExpr. + CandidateFinder finder( context, tenv, toType ); + finder.find( initExpr->expr, ResolvMode::withAdjustment() ); + + Cost minExprCost = Cost::infinity; + Cost minCastCost = Cost::infinity; + for ( CandidateRef & cand : finder.candidates ) { + if(reason.code == NotFound) reason.code = NoMatch; + + ast::TypeEnvironment env{ cand->env }; + ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have; + ast::OpenVarSet open{ cand->open }; + + PRINT( + std::cerr << " @ " << toType << " " << initAlt.designation << std::endl; + ) + + // It is possible that a cast can throw away some values in a multiply-valued + // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of + // the subexpression results that are cast directly. The candidate is invalid + // if it has fewer results than there are types to cast to. + int discardedValues = cand->expr->result->size() - toType->size(); + if ( discardedValues < 0 ) continue; + + // unification run for side-effects + bool canUnify = unify( toType, cand->expr->result, env, need, have, open ); + (void) canUnify; + Cost thisCost = computeConversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), + symtab, env ); + PRINT( + Cost legacyCost = castCost( cand->expr->result, toType, cand->expr->get_lvalue(), + symtab, env ); + std::cerr << "Considering initialization:"; + std::cerr << std::endl << " FROM: " << cand->expr->result << std::endl; + std::cerr << std::endl << " TO: " << toType << std::endl; + std::cerr << std::endl << " Unification " << (canUnify ? "succeeded" : "failed"); + std::cerr << std::endl << " Legacy cost " << legacyCost; + std::cerr << std::endl << " New cost " << thisCost; + std::cerr << std::endl; + ) + if ( thisCost != Cost::infinity ) { + // count one safe conversion for each value that is thrown away + thisCost.incSafe( discardedValues ); + if (cand->cost < minExprCost || cand->cost == minExprCost && thisCost < minCastCost) { + minExprCost = cand->cost; + minCastCost = thisCost; + matches.clear(); + } + // ambiguous case, still output candidates to print in error message + if (cand->cost == minExprCost && thisCost == minCastCost) { + CandidateRef newCand = std::make_shared( + new ast::InitExpr{ + initExpr->location, restructureCast( cand->expr, toType ), + initAlt.designation }, + std::move(env), std::move( open ), std::move( need ), cand->cost + thisCost ); + // currently assertions are always resolved immediately so this should have no effect. + // if this somehow changes in the future (e.g. delayed by indeterminate return type) + // we may need to revisit the logic. + inferParameters( newCand, matches ); + } + + } + + } + + } + + // select first on argument cost, then conversion cost + // CandidateList minArgCost = findMinCost( matches ); + // promoteCvtCost( minArgCost ); + // candidates = findMinCost( minArgCost ); + candidates = std::move(matches); + } + + void postvisit( const ast::InitExpr * ) { + assertf( false, "CandidateFinder should never see a resolved InitExpr." ); + } + + void postvisit( const ast::DeletedExpr * ) { + assertf( false, "CandidateFinder should never see a DeletedExpr." ); + } + + void postvisit( const ast::GenericExpr * ) { + assertf( false, "_Generic is not yet supported." ); + } + }; + + // size_t Finder::traceId = Stats::Heap::new_stacktrace_id("Finder"); + /// Prunes a list of candidates down to those that have the minimum conversion cost for a given + /// return type. Skips ambiguous candidates. + +} // anonymous namespace + +bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector & errors ) { + struct PruneStruct { + CandidateRef candidate; + bool ambiguous; + + PruneStruct() = default; + PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {} + }; + + // find lowest-cost candidate for each type + std::unordered_map< std::string, PruneStruct > selected; + // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found + std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;}); + for ( CandidateRef & candidate : candidates ) { + std::string mangleName; + { + ast::ptr< ast::Type > newType = candidate->expr->result; + assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get()); + candidate->env.apply( newType ); + mangleName = Mangle::mangle( newType ); + } + + auto found = selected.find( mangleName ); + if (found != selected.end() && found->second.candidate->cost < candidate->cost) { + PRINT( + std::cerr << "cost " << candidate->cost << " loses to " + << found->second.candidate->cost << std::endl; + ) + continue; + } + + // xxx - when do satisfyAssertions produce more than 1 result? + // this should only happen when initial result type contains + // unbound type parameters, then it should never be pruned by + // the previous step, since renameTyVars guarantees the mangled name + // is unique. + CandidateList satisfied; + bool needRecomputeKey = false; + if (candidate->need.empty()) { + satisfied.emplace_back(candidate); + } + else { + satisfyAssertions(candidate, context.symtab, satisfied, errors); + needRecomputeKey = true; + } + + for (auto & newCand : satisfied) { + // recomputes type key, if satisfyAssertions changed it + if (needRecomputeKey) + { + ast::ptr< ast::Type > newType = newCand->expr->result; + assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get()); + newCand->env.apply( newType ); + mangleName = Mangle::mangle( newType ); + } + auto found = selected.find( mangleName ); + if ( found != selected.end() ) { + // tiebreaking by picking the lower cost on CURRENT expression + // NOTE: this behavior is different from C semantics. + // Specific remediations are performed for C operators at postvisit(UntypedExpr). + // Further investigations may take place. + if ( newCand->cost < found->second.candidate->cost + || (newCand->cost == found->second.candidate->cost && newCand->cvtCost < found->second.candidate->cvtCost) ) { + PRINT( + std::cerr << "cost " << newCand->cost << " beats " + << found->second.candidate->cost << std::endl; + ) + + found->second = PruneStruct{ newCand }; + } else if ( newCand->cost == found->second.candidate->cost && newCand->cvtCost == found->second.candidate->cvtCost) { + // if one of the candidates contains a deleted identifier, can pick the other, + // since deleted expressions should not be ambiguous if there is another option + // that is at least as good + if ( findDeletedExpr( newCand->expr ) ) { + // do nothing + PRINT( std::cerr << "candidate is deleted" << std::endl; ) + } else if ( findDeletedExpr( found->second.candidate->expr ) ) { + PRINT( std::cerr << "current is deleted" << std::endl; ) + found->second = PruneStruct{ newCand }; + } else { + PRINT( std::cerr << "marking ambiguous" << std::endl; ) + found->second.ambiguous = true; + } + } else { + // xxx - can satisfyAssertions increase the cost? + PRINT( + std::cerr << "cost " << newCand->cost << " loses to " + << found->second.candidate->cost << std::endl; + ) + } + } else { + selected.emplace_hint( found, mangleName, newCand ); + } + } + } + + // report unambiguous min-cost candidates + // CandidateList out; + for ( auto & target : selected ) { + if ( target.second.ambiguous ) continue; + + CandidateRef cand = target.second.candidate; + + ast::ptr< ast::Type > newResult = cand->expr->result; + cand->env.applyFree( newResult ); + cand->expr = ast::mutate_field( + cand->expr.get(), &ast::Expr::result, std::move( newResult ) ); + + out.emplace_back( cand ); + } + // if everything is lost in satisfyAssertions, report the error + return !selected.empty(); +} + +void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) { + // Find alternatives for expression + ast::Pass finder{ *this }; + expr->accept( finder ); + + if ( mode.failFast && candidates.empty() ) { + switch(finder.core.reason.code) { + case Finder::NotFound: + { SemanticError( expr, "No alternatives for expression " ); break; } + case Finder::NoMatch: + { SemanticError( expr, "Invalid application of existing declaration(s) in expression " ); break; } + case Finder::ArgsToFew: + case Finder::ArgsToMany: + case Finder::RetsToFew: + case Finder::RetsToMany: + case Finder::NoReason: + default: + { SemanticError( expr->location, "No reasonable alternatives for expression : reasons unkown" ); } + } + } + + /* + if ( mode.satisfyAssns || mode.prune ) { + // trim candidates to just those where the assertions are satisfiable + // - necessary pre-requisite to pruning + CandidateList satisfied; + std::vector< std::string > errors; + for ( CandidateRef & candidate : candidates ) { + satisfyAssertions( candidate, localSyms, satisfied, errors ); + } + + // fail early if none such + if ( mode.failFast && satisfied.empty() ) { + std::ostringstream stream; + stream << "No alternatives with satisfiable assertions for " << expr << "\n"; + for ( const auto& err : errors ) { + stream << err; + } + SemanticError( expr->location, stream.str() ); + } + + // reset candidates + candidates = move( satisfied ); + } + */ + + // if ( mode.prune ) { + // optimization: don't prune for NameExpr since it never has cost + if ( mode.prune && !dynamic_cast(expr)) { + // trim candidates to single best one + PRINT( + std::cerr << "alternatives before prune:" << std::endl; + print( std::cerr, candidates ); + ) + + CandidateList pruned; + std::vector errors; + bool found = pruneCandidates( candidates, pruned, errors ); + + if ( mode.failFast && pruned.empty() ) { + std::ostringstream stream; + if (found) { + CandidateList winners = findMinCost( candidates ); + stream << "Cannot choose between " << winners.size() << " alternatives for " + "expression\n"; + ast::print( stream, expr ); + stream << " Alternatives are:\n"; + print( stream, winners, 1 ); + SemanticError( expr->location, stream.str() ); + } + else { + stream << "No alternatives with satisfiable assertions for " << expr << "\n"; + for ( const auto& err : errors ) { + stream << err; + } + SemanticError( expr->location, stream.str() ); + } + } + + auto oldsize = candidates.size(); + candidates = std::move( pruned ); + + PRINT( + std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; + ) + PRINT( + std::cerr << "there are " << candidates.size() << " alternatives after elimination" + << std::endl; + ) + } + + // adjust types after pruning so that types substituted by pruneAlternatives are correctly + // adjusted + if ( mode.adjust ) { + for ( CandidateRef & r : candidates ) { + r->expr = ast::mutate_field( + r->expr.get(), &ast::Expr::result, + adjustExprType( r->expr->result, r->env, context.symtab ) ); + } + } + + // Central location to handle gcc extension keyword, etc. for all expressions + for ( CandidateRef & r : candidates ) { + if ( r->expr->extension != expr->extension ) { + r->expr.get_and_mutate()->extension = expr->extension; + } + } +} + +std::vector< CandidateFinder > CandidateFinder::findSubExprs( + const std::vector< ast::ptr< ast::Expr > > & xs +) { + std::vector< CandidateFinder > out; + + for ( const auto & x : xs ) { + out.emplace_back( context, env ); + out.back().find( x, ResolvMode::withAdjustment() ); + + PRINT( + std::cerr << "findSubExprs" << std::endl; + print( std::cerr, out.back().candidates ); + ) + } + + return out; +} + } // namespace ResolvExpr Index: src/ResolvExpr/CandidateFinder.hpp =================================================================== --- src/ResolvExpr/CandidateFinder.hpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/CandidateFinder.hpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -33,4 +33,6 @@ const ast::TypeEnvironment & env; ///< Substitutions performed in this resolution ast::ptr< ast::Type > targetType; ///< Target type for resolution + bool strictMode = false; ///< If set to true, requires targetType to be exact match (inside return cast) + bool allowVoid = false; ///< If set to true, allow void-returning function calls (only top level, cast to void and first in comma) std::set< std::string > otypeKeys; /// different type may map to same key Index: src/ResolvExpr/CastCost.cc =================================================================== --- src/ResolvExpr/CastCost.cc (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/CastCost.cc (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -234,4 +234,7 @@ if ( typesCompatibleIgnoreQualifiers( src, dst, env ) ) { PRINT( std::cerr << "compatible!" << std::endl; ) + if (dynamic_cast(dst) || dynamic_cast(dst)) { + return Cost::spec; + } return Cost::zero; } else if ( dynamic_cast< const ast::VoidType * >( dst ) ) { Index: src/ResolvExpr/CommonType.cc =================================================================== --- src/ResolvExpr/CommonType.cc (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/CommonType.cc (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -697,4 +697,6 @@ if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) { #warning remove casts when `commonTypes` moved to new AST + + /* ast::BasicType::Kind kind = (ast::BasicType::Kind)(int)commonTypes[ (BasicType::Kind)(int)basic->kind ][ (BasicType::Kind)(int)basic2->kind ]; if ( @@ -706,4 +708,16 @@ result = new ast::BasicType{ kind, basic->qualifiers | basic2->qualifiers }; } + */ + ast::BasicType::Kind kind; + if (basic->kind != basic2->kind && !widen.first && !widen.second) return; + else if (!widen.first) kind = basic->kind; // widen.second + else if (!widen.second) kind = basic2->kind; + else kind = (ast::BasicType::Kind)(int)commonTypes[ (BasicType::Kind)(int)basic->kind ][ (BasicType::Kind)(int)basic2->kind ]; + // xxx - what does qualifiers even do here?? + if ( (basic->qualifiers >= basic2->qualifiers || widen.first) + && (basic->qualifiers <= basic2->qualifiers || widen.second) ) { + result = new ast::BasicType{ kind, basic->qualifiers | basic2->qualifiers }; + } + } else if ( dynamic_cast< const ast::ZeroType * >( type2 ) @@ -712,11 +726,14 @@ #warning remove casts when `commonTypes` moved to new AST ast::BasicType::Kind kind = (ast::BasicType::Kind)(int)commonTypes[ (BasicType::Kind)(int)basic->kind ][ (BasicType::Kind)(int)ast::BasicType::SignedInt ]; - if ( - ( ( kind == basic->kind && basic->qualifiers >= type2->qualifiers ) + /* + if ( // xxx - what does qualifier even do here?? + ( ( basic->qualifiers >= type2->qualifiers ) || widen.first ) - && ( ( kind != basic->kind && basic->qualifiers <= type2->qualifiers ) + && ( ( /* kind != basic->kind && basic->qualifiers <= type2->qualifiers ) || widen.second ) - ) { - result = new ast::BasicType{ kind, basic->qualifiers | type2->qualifiers }; + ) + */ + if (widen.second) { + result = new ast::BasicType{ basic->kind, basic->qualifiers | type2->qualifiers }; } } else if ( const ast::EnumInstType * enumInst = dynamic_cast< const ast::EnumInstType * >( type2 ) ) { @@ -746,4 +763,5 @@ auto entry = open.find( *var ); if ( entry != open.end() ) { + // if (tenv.lookup(*var)) { ast::AssertionSet need, have; if ( ! tenv.bindVar( Index: src/ResolvExpr/ConversionCost.cc =================================================================== --- src/ResolvExpr/ConversionCost.cc (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/ConversionCost.cc (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -702,4 +702,7 @@ cost = costCalc( refType->base, dst, srcIsLvalue, symtab, env ); + + // xxx - should qualifiers be considered in pass-by-value? + /* if ( refType->base->qualifiers == dst->qualifiers ) { cost.incReference(); @@ -709,4 +712,6 @@ cost.incUnsafe(); } + */ + cost.incReference(); } @@ -792,8 +797,14 @@ cost.incSign( signMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ] ); } + // this has the effect of letting any expr such as x+0, x+1 to be typed + // the same as x, instead of at least int. are we willing to sacrifice this little + // bit of coherence with C? + // TODO: currently this does not work when no zero/one overloads exist. Find a fix for it. + // cost = Cost::zero; } else if ( dynamic_cast< const ast::PointerType * >( dst ) ) { cost = Cost::zero; // +1 for zero_t ->, +1 for disambiguation cost.incSafe( maxIntCost + 2 ); + // assuming 0p is supposed to be used for pointers? } } @@ -804,5 +815,5 @@ cost = Cost::zero; } else if ( const ast::BasicType * dstAsBasic = - dynamic_cast< const ast::BasicType * >( dst ) ) { + dynamic_cast< const ast::BasicType * >( dst ) ) { int tableResult = costMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ]; if ( -1 == tableResult ) { @@ -813,4 +824,6 @@ cost.incSign( signMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ] ); } + + // cost = Cost::zero; } } Index: src/ResolvExpr/FindOpenVars.cc =================================================================== --- src/ResolvExpr/FindOpenVars.cc (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/FindOpenVars.cc (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -21,7 +21,10 @@ #include "AST/Pass.hpp" #include "AST/Type.hpp" +#include "AST/TypeEnvironment.hpp" #include "Common/PassVisitor.h" #include "SynTree/Declaration.h" // for TypeDecl, DeclarationWithType (ptr ... #include "SynTree/Type.h" // for Type, Type::ForallList, ArrayType + +#include namespace ResolvExpr { @@ -102,14 +105,21 @@ ast::AssertionSet & need; ast::AssertionSet & have; + ast::TypeEnvironment & env; bool nextIsOpen; FindOpenVars_new( ast::OpenVarSet & o, ast::OpenVarSet & c, ast::AssertionSet & n, - ast::AssertionSet & h, FirstMode firstIsOpen ) - : open( o ), closed( c ), need( n ), have( h ), nextIsOpen( firstIsOpen ) {} + ast::AssertionSet & h, ast::TypeEnvironment & env, FirstMode firstIsOpen ) + : open( o ), closed( c ), need( n ), have( h ), env (env), nextIsOpen( firstIsOpen ) {} void previsit( const ast::FunctionType * type ) { // mark open/closed variables if ( nextIsOpen ) { + // trying to remove this from resolver. + // occasionally used in other parts so not deleting right now. + + // insert open variables unbound to environment. + env.add(type->forall); + for ( auto & decl : type->forall ) { open[ *decl ] = ast::TypeData{ decl->base }; @@ -137,7 +147,15 @@ void findOpenVars( const ast::Type * type, ast::OpenVarSet & open, ast::OpenVarSet & closed, - ast::AssertionSet & need, ast::AssertionSet & have, FirstMode firstIsOpen ) { - ast::Pass< FindOpenVars_new > finder{ open, closed, need, have, firstIsOpen }; + ast::AssertionSet & need, ast::AssertionSet & have, ast::TypeEnvironment & env, FirstMode firstIsOpen ) { + ast::Pass< FindOpenVars_new > finder{ open, closed, need, have, env, firstIsOpen }; type->accept( finder ); + + if (!closed.empty()) { + std::cerr << "closed: "; + for (auto& i : closed) { + std::cerr << i.first.base->location << ":" << i.first.base->name << ' '; + } + std::cerr << std::endl; + } } } // namespace ResolvExpr Index: src/ResolvExpr/FindOpenVars.h =================================================================== --- src/ResolvExpr/FindOpenVars.h (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/FindOpenVars.h (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -33,5 +33,5 @@ void findOpenVars( const ast::Type * type, ast::OpenVarSet & open, ast::OpenVarSet & closed, - ast::AssertionSet & need, ast::AssertionSet & have, FirstMode firstIsOpen ); + ast::AssertionSet & need, ast::AssertionSet & have, ast::TypeEnvironment & env, FirstMode firstIsOpen ); } // namespace ResolvExpr Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/Resolver.cc (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -1011,4 +1011,5 @@ ast::TypeEnvironment env; CandidateFinder finder( context, env ); + finder.allowVoid = true; finder.find( untyped, recursion_level == 1 ? mode.atTopLevel() : mode ); --recursion_level; @@ -1054,5 +1055,5 @@ // promote candidate.cvtCost to .cost - promoteCvtCost( winners ); + // promoteCvtCost( winners ); // produce ambiguous errors, if applicable Index: src/ResolvExpr/SatisfyAssertions.cpp =================================================================== --- src/ResolvExpr/SatisfyAssertions.cpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/SatisfyAssertions.cpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -16,4 +16,5 @@ #include "SatisfyAssertions.hpp" +#include #include #include @@ -45,4 +46,6 @@ #include "SymTab/Mangler.h" + + namespace ResolvExpr { @@ -65,5 +68,9 @@ ast::AssertionSet && h, ast::AssertionSet && n, ast::OpenVarSet && o, ast::UniqueId rs ) : cdata( c ), adjType( at ), env( std::move( e ) ), have( std::move( h ) ), - need( std::move( n ) ), open( std::move( o ) ), resnSlot( rs ) {} + need( std::move( n ) ), open( std::move( o ) ), resnSlot( rs ) { + if (!have.empty()) { + std::cerr << c.id->location << ':' << c.id->name << std::endl; + } + } }; @@ -139,10 +146,5 @@ }; - /// Adds a captured assertion to the symbol table - void addToSymbolTable( const ast::AssertionSet & have, ast::SymbolTable & symtab ) { - for ( auto & i : have ) { - if ( i.second.isUsed ) { symtab.addId( i.first->var ); } - } - } + enum AssertionResult {Fail, Skip, Success} ; /// Binds a single assertion, updating satisfaction state @@ -155,5 +157,5 @@ "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() ); - ast::Expr * varExpr = match.cdata.combine( cand->expr->location, cand->cvtCost ); + ast::Expr * varExpr = match.cdata.combine( cand->expr->location, cand->cost ); varExpr->result = match.adjType; if ( match.resnSlot ) { varExpr->inferred.resnSlots().emplace_back( match.resnSlot ); } @@ -165,10 +167,13 @@ /// Satisfy a single assertion - bool satisfyAssertion( ast::AssertionList::value_type & assn, SatState & sat, bool allowConversion = false, bool skipUnbound = false) { + AssertionResult satisfyAssertion( ast::AssertionList::value_type & assn, SatState & sat, bool skipUnbound = false) { // skip unused assertions - if ( ! assn.second.isUsed ) return true; + static unsigned int cnt = 0; + if ( ! assn.second.isUsed ) return AssertionResult::Success; + + if (assn.first->var->name[1] == '|') std::cerr << ++cnt << std::endl; // find candidates that unify with the desired type - AssnCandidateList matches; + AssnCandidateList matches, inexactMatches; std::vector candidates; @@ -179,10 +184,15 @@ .strict_as()->params[0] .strict_as()->base; - sat.cand->env.apply(thisArgType); + // sat.cand->env.apply(thisArgType); + + if (auto inst = thisArgType.as()) { + auto cls = sat.cand->env.lookup(*inst); + if (cls && cls->bound) thisArgType = cls->bound; + } std::string otypeKey = ""; if (thisArgType.as()) otypeKey = Mangle::Encoding::pointer; else if (!isUnboundType(thisArgType)) otypeKey = Mangle::mangle(thisArgType, Mangle::Type | Mangle::NoGenericParams); - else if (skipUnbound) return false; + else if (skipUnbound) return AssertionResult::Skip; candidates = sat.symtab.specialLookupId(kind, otypeKey); @@ -212,7 +222,24 @@ ast::OpenVarSet closed; - findOpenVars( toType, newOpen, closed, newNeed, have, FirstClosed ); - findOpenVars( adjType, newOpen, closed, newNeed, have, FirstOpen ); - if ( allowConversion ) { + // findOpenVars( toType, newOpen, closed, newNeed, have, FirstClosed ); + findOpenVars( adjType, newOpen, closed, newNeed, have, newEnv, FirstOpen ); + ast::TypeEnvironment tempNewEnv {newEnv}; + + if ( unifyExact( toType, adjType, tempNewEnv, newNeed, have, newOpen, WidenMode {true, true} ) ) { + // set up binding slot for recursive assertions + ast::UniqueId crntResnSlot = 0; + if ( ! newNeed.empty() ) { + crntResnSlot = ++globalResnSlot; + for ( auto & a : newNeed ) { a.second.resnSlot = crntResnSlot; } + } + + matches.emplace_back( + cdata, adjType, std::move( tempNewEnv ), std::move( have ), std::move( newNeed ), + std::move( newOpen ), crntResnSlot ); + } + else if ( matches.empty() ) { + // restore invalidated env + // newEnv = sat.cand->env; + // newNeed.clear(); if ( auto c = commonType( toType, adjType, newEnv, newNeed, have, newOpen, WidenMode {true, true} ) ) { // set up binding slot for recursive assertions @@ -223,37 +250,24 @@ } - matches.emplace_back( + inexactMatches.emplace_back( cdata, adjType, std::move( newEnv ), std::move( have ), std::move( newNeed ), std::move( newOpen ), crntResnSlot ); } } - else { - if ( unifyExact( toType, adjType, newEnv, newNeed, have, newOpen, WidenMode {true, true} ) ) { - // set up binding slot for recursive assertions - ast::UniqueId crntResnSlot = 0; - if ( ! newNeed.empty() ) { - crntResnSlot = ++globalResnSlot; - for ( auto & a : newNeed ) { a.second.resnSlot = crntResnSlot; } - } - - matches.emplace_back( - cdata, adjType, std::move( newEnv ), std::move( have ), std::move( newNeed ), - std::move( newOpen ), crntResnSlot ); - } - } } // break if no satisfying match - if ( matches.empty() ) return false; + if ( matches.empty() ) matches = std::move(inexactMatches); + if ( matches.empty() ) return AssertionResult::Fail; // defer if too many satisfying matches if ( matches.size() > 1 ) { sat.deferred.emplace_back( assn.first, assn.second, std::move( matches ) ); - return true; + return AssertionResult::Success; } // otherwise bind unique match in ongoing scope AssnCandidate & match = matches.front(); - addToSymbolTable( match.have, sat.symtab ); + // addToSymbolTable( match.have, sat.symtab ); sat.newNeed.insert( match.need.begin(), match.need.end() ); sat.cand->env = std::move( match.env ); @@ -261,5 +275,5 @@ bindAssertion( assn.first, assn.second, sat.cand, match, sat.inferred ); - return true; + return AssertionResult::Success; } @@ -438,5 +452,4 @@ // for each current mutually-compatible set of assertions for ( SatState & sat : sats ) { - bool allowConversion = false; // stop this branch if a better option is already found auto it = thresholds.find( pruneKey( *sat.cand ) ); @@ -447,18 +460,10 @@ for (unsigned resetCount = 0; ; ++resetCount) { ast::AssertionList next; - resetTyVarRenaming(); // make initial pass at matching assertions for ( auto & assn : sat.need ) { + resetTyVarRenaming(); // fail early if any assertion is not satisfiable - if ( ! satisfyAssertion( assn, sat, allowConversion, !next.empty() ) ) { - next.emplace_back(assn); - // goto nextSat; - } - } - // success - if (next.empty()) break; - // fail if nothing resolves - else if (next.size() == sat.need.size()) { - if (allowConversion) { + auto result = satisfyAssertion( assn, sat, !next.empty() ); + if ( result == AssertionResult::Fail ) { Indenter tabs{ 3 }; std::ostringstream ss; @@ -466,16 +471,17 @@ print( ss, *sat.cand, ++tabs ); ss << (tabs-1) << "Could not satisfy assertion:\n"; - ast::print( ss, next[0].first, tabs ); + ast::print( ss, assn.first, tabs ); errors.emplace_back( ss.str() ); goto nextSat; } - - else { - allowConversion = true; - continue; - } - } - allowConversion = false; + else if ( result == AssertionResult::Skip ) { + next.emplace_back(assn); + // goto nextSat; + } + } + // success + if (next.empty()) break; + sat.need = std::move(next); } @@ -531,5 +537,5 @@ sat.cand->expr, std::move( compat.env ), std::move( compat.open ), ast::AssertionSet{} /* need moved into satisfaction state */, - sat.cand->cost, sat.cand->cvtCost ); + sat.cand->cost ); ast::AssertionSet nextNewNeed{ sat.newNeed }; @@ -544,5 +550,5 @@ for ( DeferRef r : compat.assns ) { AssnCandidate match = r.match; - addToSymbolTable( match.have, nextSymtab ); + // addToSymbolTable( match.have, nextSymtab ); nextNewNeed.insert( match.need.begin(), match.need.end() ); Index: src/ResolvExpr/Unify.cc =================================================================== --- src/ResolvExpr/Unify.cc (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/ResolvExpr/Unify.cc (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -160,6 +160,6 @@ env.apply( newSecond ); - findOpenVars( newFirst, open, closed, need, have, FirstClosed ); - findOpenVars( newSecond, open, closed, need, have, FirstOpen ); + // findOpenVars( newFirst, open, closed, need, have, FirstClosed ); + findOpenVars( newSecond, open, closed, need, have, newEnv, FirstOpen ); return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden() ); @@ -964,5 +964,6 @@ // check that the other type is compatible and named the same auto otherInst = dynamic_cast< const XInstType * >( other ); - if (otherInst && inst->name == otherInst->name) this->result = otherInst; + if (otherInst && inst->name == otherInst->name) + this->result = otherInst; return otherInst; } @@ -1049,6 +1050,9 @@ void postvisit( const ast::TypeInstType * typeInst ) { - assert( open.find( *typeInst ) == open.end() ); - handleRefType( typeInst, type2 ); + // assert( open.find( *typeInst ) == open.end() ); + auto otherInst = dynamic_cast< const ast::TypeInstType * >( type2 ); + if (otherInst && typeInst->name == otherInst->name) + this->result = otherInst; + // return otherInst; } @@ -1161,6 +1165,6 @@ ) { ast::OpenVarSet closed; - findOpenVars( type1, open, closed, need, have, FirstClosed ); - findOpenVars( type2, open, closed, need, have, FirstOpen ); + // findOpenVars( type1, open, closed, need, have, FirstClosed ); + findOpenVars( type2, open, closed, need, have, env, FirstOpen ); return unifyInexact( type1, type2, env, need, have, open, WidenMode{ true, true }, common ); @@ -1179,7 +1183,10 @@ entry1 = var1 ? open.find( *var1 ) : open.end(), entry2 = var2 ? open.find( *var2 ) : open.end(); - bool isopen1 = entry1 != open.end(); - bool isopen2 = entry2 != open.end(); - + // bool isopen1 = entry1 != open.end(); + // bool isopen2 = entry2 != open.end(); + bool isopen1 = var1 && env.lookup(*var1); + bool isopen2 = var2 && env.lookup(*var2); + + /* if ( isopen1 && isopen2 ) { if ( entry1->second.kind != entry2->second.kind ) return false; @@ -1190,9 +1197,20 @@ return env.bindVar( var1, type2, entry1->second, need, have, open, widen ); } else if ( isopen2 ) { - return env.bindVar( var2, type1, entry2->second, need, have, open, widen ); - } else { + return env.bindVar( var2, type1, entry2->second, need, have, open, widen, symtab ); + } */ + if ( isopen1 && isopen2 ) { + if ( var1->base->kind != var2->base->kind ) return false; + return env.bindVarToVar( + var1, var2, ast::TypeData{ var1->base->kind, var1->base->sized||var2->base->sized }, need, have, + open, widen ); + } else if ( isopen1 ) { + return env.bindVar( var1, type2, ast::TypeData{var1->base}, need, have, open, widen ); + } else if ( isopen2 ) { + return env.bindVar( var2, type1, ast::TypeData{var2->base}, need, have, open, widen ); + }else { return ast::Pass::read( type1, type2, env, need, have, open, widen ); } + } Index: src/SynTree/Expression.cc =================================================================== --- src/SynTree/Expression.cc (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/SynTree/Expression.cc (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -267,13 +267,13 @@ } -CastExpr::CastExpr( Expression * arg, Type * toType, bool isGenerated ) : arg(arg), isGenerated( isGenerated ) { +CastExpr::CastExpr( Expression * arg, Type * toType, bool isGenerated, CastKind kind ) : arg(arg), isGenerated( isGenerated ), kind( kind ) { set_result(toType); } -CastExpr::CastExpr( Expression * arg, bool isGenerated ) : arg(arg), isGenerated( isGenerated ) { +CastExpr::CastExpr( Expression * arg, bool isGenerated, CastKind kind ) : arg(arg), isGenerated( isGenerated ), kind( kind ) { set_result( new VoidType( Type::Qualifiers() ) ); } -CastExpr::CastExpr( const CastExpr & other ) : Expression( other ), arg( maybeClone( other.arg ) ), isGenerated( other.isGenerated ) { +CastExpr::CastExpr( const CastExpr & other ) : Expression( other ), arg( maybeClone( other.arg ) ), isGenerated( other.isGenerated ), kind( other.kind ) { } Index: src/SynTree/Expression.h =================================================================== --- src/SynTree/Expression.h (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/SynTree/Expression.h (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -271,6 +271,14 @@ bool isGenerated = true; - CastExpr( Expression * arg, bool isGenerated = true ); - CastExpr( Expression * arg, Type * toType, bool isGenerated = true ); + enum CastKind { + Default, // C + Coerce, // reinterpret cast + Return // overload selection + }; + + CastKind kind = Default; + + CastExpr( Expression * arg, bool isGenerated = true, CastKind kind = Default ); + CastExpr( Expression * arg, Type * toType, bool isGenerated = true, CastKind kind = Default ); CastExpr( Expression * arg, void * ) = delete; // prevent accidentally passing pointers for isGenerated in the first constructor CastExpr( const CastExpr & other ); Index: src/Tuples/TupleAssignment.cc =================================================================== --- src/Tuples/TupleAssignment.cc (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/Tuples/TupleAssignment.cc (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -679,4 +679,5 @@ ResolvExpr::CandidateFinder finder( crntFinder.context, matcher->env ); + finder.allowVoid = true; try { Index: src/Validate/Autogen.cpp =================================================================== --- src/Validate/Autogen.cpp (revision 251ce804bfa9c794ec6fdf5d077a6553e6d749a4) +++ src/Validate/Autogen.cpp (revision 24d6572fc571b2a894d56a9335edd57899c448c0) @@ -321,4 +321,16 @@ void FuncGenerator::produceDecl( const ast::FunctionDecl * decl ) { assert( nullptr != decl->stmts ); + const auto & oldParams = getGenericParams(type); + assert( decl->type_params.size() == oldParams.size()); + + /* + ast::DeclReplacer::TypeMap typeMap; + for (auto it = oldParams.begin(), jt = decl->type_params.begin(); it != oldParams.end(); ++it, ++jt) { + typeMap.emplace(*it, *jt); + } + + const ast::FunctionDecl * mut = strict_dynamic_cast(ast::DeclReplacer::replace(decl, typeMap)); + assert (mut == decl); + */ definitions.push_back( decl ); @@ -352,4 +364,6 @@ std::vector> type_params; std::vector> assertions; + + ast::DeclReplacer::TypeMap typeMap; for ( auto & old_param : old_type_params ) { ast::TypeDecl * decl = ast::deepCopy( old_param ); @@ -358,4 +372,12 @@ oldToNew.emplace( std::make_pair( old_param, decl ) ); type_params.push_back( decl ); + typeMap.emplace(old_param, decl); + } + + for (auto & param : params) { + param = ast::DeclReplacer::replace(param, typeMap); + } + for (auto & param : returns) { + param = ast::DeclReplacer::replace(param, typeMap); } replaceAll( params, oldToNew ); @@ -522,5 +544,5 @@ InitTweak::InitExpander_new srcParam( src ); // Assign to destination. - ast::Expr * dstSelect = new ast::MemberExpr( + ast::MemberExpr * dstSelect = new ast::MemberExpr( location, field, @@ -574,5 +596,5 @@ } - ast::Expr * srcSelect = (srcParam) ? new ast::MemberExpr( + ast::MemberExpr * srcSelect = (srcParam) ? new ast::MemberExpr( location, field, new ast::VariableExpr( location, srcParam ) ) : nullptr;