Changes in src/ResolvExpr/AlternativeFinder.cc [fae6f21:11094d9]

File:

• src/ResolvExpr/AlternativeFinder.cc (modified) (40 diffs)

src/ResolvExpr/AlternativeFinder.cc

@@ -76 +76 @@
 
         namespace {
-                void printAlts( const AltList &list, std::ostream &os, int indent = 0 ) {
+                void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt = 0 ) {
+                        Indenter indent = { Indenter::tabsize, indentAmt };
                         for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
                                 i->print( os, indent );
@@ -122 +123 @@
                                                 )
                                                 mapPlace->second.isAmbiguous = true;
+                                        } else {
+                                                PRINT(
+                                                        std::cerr << "cost " << candidate->cost << " loses to " << mapPlace->second.candidate->cost << std::endl;
+                                                )
                                         }
                                 } else {
@@ -127 +132 @@
                                 }
                         }
-
-                        PRINT(
-                                std::cerr << "there are " << selected.size() << " alternatives before elimination" << std::endl;
-                        )
 
                         // accept the alternatives that were unambiguous
@@ -145 +146 @@
                         expr->get_result()->accept( global_renamer );
                 }
-
-                void referenceToRvalueConversion( Expression *& expr ) {
-                        if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
-                                // cast away reference from expr
-                                expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() );
-                        }
-                }
         } // namespace
+
+        void referenceToRvalueConversion( Expression *& expr ) {
+                if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
+                        // cast away reference from expr
+                        expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() );
+                }
+        }
 
         template< typename InputIterator, typename OutputIterator >
@@ -175 +176 @@
         }
 
-        void AlternativeFinder::find( Expression *expr, bool adjust, bool prune ) {
+        void AlternativeFinder::find( Expression *expr, bool adjust, bool prune, bool failFast ) {
                 expr->accept( *this );
-                if ( alternatives.empty() ) {
+                if ( failFast && alternatives.empty() ) {
                         throw SemanticError( "No reasonable alternatives for expression ", expr );
                 }
-                for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
-                        if ( adjust ) {
-                                adjustExprType( i->expr->get_result(), i->env, indexer );
-                        }
-                }
                 if ( prune ) {
+                        auto oldsize = alternatives.size();
                         PRINT(
                                 std::cerr << "alternatives before prune:" << std::endl;
@@ -192 +189 @@
                         AltList::iterator oldBegin = alternatives.begin();
                         pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) );
-                        if ( alternatives.begin() == oldBegin ) {
+                        if ( failFast && alternatives.begin() == oldBegin ) {
                                 std::ostringstream stream;
                                 AltList winners;
                                 findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
-                                stream << "Cannot choose between " << winners.size() << " alternatives for expression ";
+                                stream << "Cannot choose between " << winners.size() << " alternatives for expression\n";
                                 expr->print( stream );
-                                stream << "Alternatives are:";
-                                printAlts( winners, stream, 8 );
+                                stream << "Alternatives are:\n";
+                                printAlts( winners, stream, 1 );
                                 throw SemanticError( stream.str() );
                         }
                         alternatives.erase( oldBegin, alternatives.end() );
+                        PRINT(
+                                std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
+                        )
                         PRINT(
                                 std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
                         )
+                }
+                // adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted
+                for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
+                        if ( adjust ) {
+                                adjustExprType( i->expr->get_result(), i->env, indexer );
+                        }
                 }
 
@@ -215 +221 @@
         }
 
-        void AlternativeFinder::findWithAdjustment( Expression *expr, bool prune ) {
-                find( expr, true, prune );
+        void AlternativeFinder::findWithAdjustment( Expression *expr ) {
+                find( expr, true );
+        }
+
+        void AlternativeFinder::findWithoutPrune( Expression * expr ) {
+                find( expr, true, false );
+        }
+
+        void AlternativeFinder::maybeFind( Expression * expr ) {
+                find( expr, true, true, false );
         }
 
@@ -299 +313 @@
                 Cost convCost = conversionCost( actualType, formalType, indexer, env );
                 PRINT(
-                        std::cerr << std::endl << "cost is" << convCost << std::endl;
+                        std::cerr << std::endl << "cost is " << convCost << std::endl;
                 )
                 if ( convCost == Cost::infinity ) {
@@ -305 +319 @@
                 }
                 convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) );
+                PRINT(
+                        std::cerr << "cost with polycost is " << convCost << std::endl;
+                )
                 return convCost;
         }
@@ -310 +327 @@
         Cost computeExpressionConversionCost( Expression *& actualExpr, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
                 Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env );
-                // if ( convCost != Cost::zero ) {
-
-                // xxx - temporary -- ignore poly cost, since this causes some polymorphic functions to be cast, which causes the specialize
-                // pass to try to specialize them, which currently does not work. Once that is fixed, remove the next 3 lines and uncomment the
-                // previous line.
+
+                // 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() );
@@ -357 +373 @@
                                 if ( function->get_isVarArgs() ) {
                                         convCost.incUnsafe();
+                                        PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; )
                                         // convert reference-typed expressions to value-typed expressions
                                         referenceToRvalueConversion( *actualExpr );
@@ -365 +382 @@
                         }
                         Type * formalType = (*formal)->get_type();
-                        PRINT(
-                                std::cerr << std::endl << "converting ";
-                                actualType->print( std::cerr, 8 );
-                                std::cerr << std::endl << " to ";
-                                formalType->print( std::cerr, 8 );
-                                std::cerr << std::endl << "environment is: ";
-                                alt.env.print( std::cerr, 8 );
-                                std::cerr << std::endl;
-                        )
                         convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
                         ++formal; // can't be in for-loop update because of the continue
@@ -481 +489 @@
                                 Alternative newerAlt( newAlt );
                                 newerAlt.env = newEnv;
-                                assert( (*candidate)->get_uniqueId() );
+                                assertf( (*candidate)->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( *candidate ).c_str() );
                                 DeclarationWithType *candDecl = static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );
 
@@ -507 +515 @@
                                         std::cerr << std::endl;
                                 )
-                                ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr );
                                 // follow the current assertion's ID chain to find the correct set of inferred parameters to add the candidate to (i.e. the set of inferred parameters belonging to the entity which requested the assertion parameter).
-                                InferredParams * inferParameters = &appExpr->get_inferParams();
+                                InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
                                 for ( UniqueId id : cur->second.idChain ) {
                                         inferParameters = (*inferParameters)[ id ].inferParams.get();
@@ -574 +581 @@
                 std::vector<unsigned> tupleEls;  /// Number of elements in current tuple element(s)
 
-                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, 
+                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
                                 const OpenVarSet& openVars)
                         : actuals(), env(env), need(need), have(have), openVars(openVars), nextArg(0),
                           expls(), nextExpl(0), tupleEls() {}
-                
+
                 /// Starts a new tuple expression
                 void beginTuple() {
@@ -613 +620 @@
 
         /// Instantiates an argument to match a formal, returns false if no results left
-        bool instantiateArgument( Type* formalType, Initializer* initializer, 
-                        const std::vector< AlternativeFinder >& args, 
-                        std::vector<ArgPack>& results, std::vector<ArgPack>& nextResults, 
+        bool instantiateArgument( Type* formalType, Initializer* initializer,
+                        const std::vector< AlternativeFinder >& args,
+                        std::vector<ArgPack>& results, std::vector<ArgPack>& nextResults,
                         const SymTab::Indexer& indexer ) {
                 if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) {
@@ -622 +629 @@
                         for ( Type* type : *tupleType ) {
                                 // xxx - dropping initializer changes behaviour from previous, but seems correct
-                                if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) ) 
+                                if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) )
                                         return false;
                         }
@@ -651 +658 @@
                                                 Type* argType = result.actuals.back().expr->get_result();
                                                 if ( result.tupleEls.back() == 1 && Tuples::isTtype( argType ) ) {
-                                                        // the case where a ttype value is passed directly is special, e.g. for 
+                                                        // 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 
+                                                        // xxx - what would happen if unify was changed so that unifying tuple
                                                         // types flattened both before unifying lists? then pass in TupleType
                                                         // (ttype) below.
@@ -664 +671 @@
                                                 }
                                                 // check unification for ttype before adding to final
-                                                if ( unify( ttype, argType, result.env, result.need, result.have, 
+                                                if ( unify( ttype, argType, result.env, result.need, result.have,
                                                                 result.openVars, indexer ) ) {
                                                         finalResults.push_back( std::move(result) );
@@ -677 +684 @@
                                                 aResult.env.addActual( actual.env, aResult.openVars );
                                                 Cost cost = actual.cost;
-                
+
                                                 // explode argument
                                                 std::vector<Alternative> exploded;
                                                 Tuples::explode( actual, indexer, back_inserter( exploded ) );
-                                                
+
                                                 // add exploded argument to tuple
                                                 for ( Alternative& aActual : exploded ) {
@@ -699 +706 @@
                         return ! results.empty();
                 }
-                
+
                 // iterate each current subresult
                 for ( unsigned iResult = 0; iResult < results.size(); ++iResult ) {
@@ -717 +724 @@
                                         std::cerr << std::endl;
                                 )
-                                
-                                if ( unify( formalType, actualType, result.env, result.need, result.have, 
+
+                                if ( unify( formalType, actualType, result.env, result.need, result.have,
                                                 result.openVars, indexer ) ) {
                                         ++result.nextExpl;
@@ -729 +736 @@
                                 if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
                                         if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
-                                                if ( unify( formalType, cnst->get_type(), result.env, result.need, 
+                                                if ( unify( formalType, cnst->get_type(), result.env, result.need,
                                                                 result.have, result.openVars, indexer ) ) {
                                                         nextResults.push_back( std::move(result.withArg( cnstExpr )) );
@@ -784 +791 @@
                 results.swap( nextResults );
                 nextResults.clear();
-                
+
                 return ! results.empty();
         }
 
         template<typename OutputIterator>
-        void AlternativeFinder::makeFunctionAlternatives( const Alternative& func, 
-                        FunctionType* funcType, const std::vector< AlternativeFinder >& args, 
+        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func,
+                        FunctionType *funcType, const std::vector< AlternativeFinder > &args,
                         OutputIterator out ) {
                 OpenVarSet funcOpenVars;
                 AssertionSet funcNeed, funcHave;
-                TypeEnvironment funcEnv;
+                TypeEnvironment funcEnv( func.env );
                 makeUnifiableVars( funcType, funcOpenVars, funcNeed );
-                // add all type variables as open variables now so that those not used in the parameter 
+                // add all type variables as open variables now so that those not used in the parameter
                 // list are still considered open.
                 funcEnv.add( funcType->get_forall() );
@@ -802 +809 @@
                 if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
                         // attempt to narrow based on expected target type
-                        Type* returnType = funcType->get_returnVals().front()->get_type();
-                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars, 
+                        Type * returnType = funcType->get_returnVals().front()->get_type();
+                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
                                         indexer ) ) {
                                 // unification failed, don't pursue this function alternative
@@ -815 +822 @@
                 for ( DeclarationWithType* formal : funcType->get_parameters() ) {
                         ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
-                        if ( ! instantiateArgument( 
+                        if ( ! instantiateArgument(
                                         obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) )
                                 return;
@@ -897 +904 @@
 
                 std::vector< AlternativeFinder > argAlternatives;
-                findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), 
+                findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
                         back_inserter( argAlternatives ) );
 
@@ -905 +912 @@
 
                 // find function operators
+                static NameExpr *opExpr = new NameExpr( "?()" );
                 AlternativeFinder funcOpFinder( indexer, env );
-                NameExpr *opExpr = new NameExpr( "?()" );
-                try {
-                        funcOpFinder.findWithAdjustment( opExpr );
-                } catch( SemanticError &e ) {
-                        // it's ok if there aren't any defined function ops
-                }
+                // it's ok if there aren't any defined function ops
+                funcOpFinder.maybeFind( opExpr);
                 PRINT(
                         std::cerr << "known function ops:" << std::endl;
-                        printAlts( funcOpFinder.alternatives, std::cerr, 8 );
+                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
                 )
 
@@ -930 +934 @@
                                                 Alternative newFunc( *func );
                                                 referenceToRvalueConversion( newFunc.expr );
-                                                makeFunctionAlternatives( newFunc, function, argAlternatives, 
+                                                makeFunctionAlternatives( newFunc, function, argAlternatives,
                                                         std::back_inserter( candidates ) );
                                         }
@@ -939 +943 @@
                                                         Alternative newFunc( *func );
                                                         referenceToRvalueConversion( newFunc.expr );
-                                                        makeFunctionAlternatives( newFunc, function, argAlternatives, 
+                                                        makeFunctionAlternatives( newFunc, function, argAlternatives,
                                                                 std::back_inserter( candidates ) );
                                                 } // if
                                         } // if
-                                }                       
+                                }
                         } catch ( SemanticError &e ) {
                                 errors.append( e );
@@ -958 +962 @@
                                 try {
                                         // check if type is a pointer to function
-                                        if ( PointerType* pointer = dynamic_cast<PointerType*>( 
+                                        if ( PointerType* pointer = dynamic_cast<PointerType*>(
                                                         funcOp->expr->get_result()->stripReferences() ) ) {
-                                                if ( FunctionType* function = 
+                                                if ( FunctionType* function =
                                                                 dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
                                                         Alternative newFunc( *funcOp );
                                                         referenceToRvalueConversion( newFunc.expr );
-                                                        makeFunctionAlternatives( newFunc, function, argAlternatives, 
+                                                        makeFunctionAlternatives( newFunc, function, argAlternatives,
                                                                 std::back_inserter( candidates ) );
                                                 }
@@ -1003 +1007 @@
                 candidates.splice( candidates.end(), alternatives );
 
-                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
+                // use a new list so that alternatives are not examined by addAnonConversions twice.
+                AltList winners;
+                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
 
                 // function may return struct or union value, in which case we need to add alternatives for implicit
                 // conversions to each of the anonymous members, must happen after findMinCost since anon conversions
                 // are never the cheapest expression
-                for ( const Alternative & alt : alternatives ) {
+                for ( const Alternative & alt : winners ) {
                         addAnonConversions( alt );
                 }
+                alternatives.splice( alternatives.begin(), winners );
 
                 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
@@ -1028 +1035 @@
         bool isLvalue( Expression *expr ) {
                 // xxx - recurse into tuples?
-                return expr->has_result() && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
+                return expr->result && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
         }
 
@@ -1103 +1110 @@
                                 thisCost.incSafe( discardedValues );
                                 Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost );
-                                // xxx - this doesn't work at the moment, since inferParameters requires an ApplicationExpr as the alternative.
-                                // Once this works, it should be possible to infer parameters on a cast expression and specialize any function.
-
-                                // inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
-                                candidates.emplace_back( std::move( newAlt ) );
+                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
                         } // if
                 } // for
@@ -1123 +1126 @@
                 AlternativeFinder finder( indexer, env );
                 // don't prune here, since it's guaranteed all alternatives will have the same type
-                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
-                finder.findWithAdjustment( castExpr->get_arg(), false );
+                finder.findWithoutPrune( castExpr->get_arg() );
                 for ( Alternative & alt : finder.alternatives ) {
                         alternatives.push_back( Alternative(
@@ -1163 +1165 @@
                 PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
                 for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
-                        VariableExpr newExpr( *i, nameExpr->get_argName() );
+                        VariableExpr newExpr( *i );
                         alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
                         PRINT(
@@ -1398 +1400 @@
                 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
                 std::list< AltList > possibilities;
-                // TODO re-write to use iterative method
                 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
                 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
@@ -1422 +1423 @@
                 // don't prune here, since it's guaranteed all alternatives will have the same type
                 // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
-                finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
+                finder.findWithoutPrune( ctorExpr->get_callExpr() );
                 for ( Alternative & alt : finder.alternatives ) {
                         alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
@@ -1459 +1460 @@
                 // O(N^2) checks of d-types with e-types
                 for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
-                        Type * toType = resolveTypeof( initAlt.type, indexer );
+                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
                         SymTab::validateType( toType, &indexer );
                         adjustExprType( toType, env, indexer );
@@ -1488 +1489 @@
                                         // count one safe conversion for each value that is thrown away
                                         thisCost.incSafe( discardedValues );
-                                        candidates.push_back( Alternative( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost ) );
+                                        Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost );
+                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
                                 }
                         }