Changeset 46da46b for src/ResolvExpr/CandidateFinder.cpp

Timestamp:

May 2, 2023, 3:44:31 AM (14 months ago)

Author:

Fangren Yu <f37yu@…>

Branches:

ast-experimental, master

Children:

0c840fc

Parents:

1ab773e0

Message:

current progress

File:

• src/ResolvExpr/CandidateFinder.cpp (modified) (19 diffs)

src/ResolvExpr/CandidateFinder.cpp

@@ -30 +30 @@
 #include "Resolver.h"
 #include "ResolveTypeof.h"
+#include "WidenMode.h"
 #include "SatisfyAssertions.hpp"
 #include "typeops.h"              // for adjustExprType, conversionCost, polyCost, specCost
@@ -700 +701 @@
                                 // attempt to narrow based on expected target type
                                 const ast::Type * returnType = funcType->returns.front();
-                                if ( ! unify(
-                                        returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab )
-                                ) {
-                                        // unification failed, do not pursue this candidate
-                                        return;
+                                if ( selfFinder.strictMode ) {
+                                        if ( ! unifyExact(
+                                                returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, noWiden(), symtab ) // xxx - is no widening correct?
+                                        ) {
+                                                // unification failed, do not pursue this candidate
+                                                return;
+                                        }
+                                }
+                                else {
+                                        if ( ! unify(
+                                                returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab )
+                                        ) {
+                                                // unification failed, do not pursue this candidate
+                                                return;
+                                        }
                                 }
                         }
@@ -825 +836 @@
 
                         if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {
-                                addAggMembers( structInst, aggrExpr, *cand, Cost::safe, "" );
+                                addAggMembers( structInst, aggrExpr, *cand, Cost::unsafe, "" );
                         } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {
-                                addAggMembers( unionInst, aggrExpr, *cand, Cost::safe, "" );
+                                addAggMembers( unionInst, aggrExpr, *cand, Cost::unsafe, "" );
                         }
                 }
@@ -958 +969 @@
                                         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 =
@@ -1008 +1020 @@
                         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 ) {
@@ -1030 +1047 @@
                                 if ( cvtCost != Cost::infinity ) {
                                         withFunc->cvtCost = cvtCost;
-                                        candidates.emplace_back( std::move( withFunc ) );
-                                }
-                        }
+                                        withFunc->cost += cvtCost;      
+                                        auto func = withFunc->expr.strict_as<ast::ApplicationExpr>()->func.as<ast::VariableExpr>();
+                                        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 );
+                        // 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 ) {
+                        for ( const CandidateRef & c : found ) {
                                 addAnonConversions( c );
                         }
-                        spliceBegin( candidates, winners );
-
-                        if ( candidates.empty() && targetType && ! targetType->isVoid() ) {
+                        // 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.
@@ -1093 +1125 @@
 
                         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() );
 
@@ -1098 +1140 @@
 
                         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;
@@ -1129 +1173 @@
                                         // count one safe conversion for each value that is thrown away
                                         thisCost.incSafe( discardedValues );
-                                        CandidateRef newCand = std::make_shared<Candidate>(
-                                                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 );
+                                        // 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<Candidate>(
+                                                        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 );
                 }
 
@@ -1261 +1320 @@
 
                                 CandidateRef newCand = std::make_shared<Candidate>(
-                                        newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero,
-                                        cost );
+                                        newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, cost );
 
                                 if (newCand->expr->env) {
@@ -1407 +1465 @@
                         // candidates for true result
                         CandidateFinder finder2( context, tenv );
+                        finder2.allowVoid = true;
                         finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
                         if ( finder2.candidates.empty() ) return;
@@ -1412 +1471 @@
                         // candidates for false result
                         CandidateFinder finder3( context, tenv );
+                        finder3.allowVoid = true;
                         finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
                         if ( finder3.candidates.empty() ) return;
@@ -1478 +1538 @@
                 void postvisit( const ast::ConstructorExpr * ctorExpr ) {
                         CandidateFinder finder( context, tenv );
+                        finder.allowVoid = true;
                         finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
                         for ( CandidateRef & r : finder.candidates ) {
@@ -1594 +1655 @@
                                 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;
@@ -1631 +1695 @@
                                                 // count one safe conversion for each value that is thrown away
                                                 thisCost.incSafe( discardedValues );
-                                                CandidateRef newCand = std::make_shared<Candidate>(
+                                                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<Candidate>(
                                                         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 );
-                                        }
+                                                        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 );
+                                                }
+
+                                        }
+                                        
                                 }
 
@@ -1643 +1720 @@
 
                         // select first on argument cost, then conversion cost
-                        CandidateList minArgCost = findMinCost( matches );
-                        promoteCvtCost( minArgCost );
-                        candidates = findMinCost( minArgCost );
+                        // CandidateList minArgCost = findMinCost( matches );
+                        // promoteCvtCost( minArgCost );
+                        // candidates = findMinCost( minArgCost );
+                        candidates = std::move(matches);
                 }
 
@@ -1724 +1802 @@
                         auto found = selected.find( mangleName );
                         if ( found != selected.end() ) {
-                                if ( newCand->cost < found->second.candidate->cost ) {
+                                // 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 "
@@ -1731 +1814 @@
 
                                         found->second = PruneStruct{ newCand };
-                                } else if ( newCand->cost == found->second.candidate->cost ) {
+                                } 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
@@ -1822 +1905 @@
         */
 
-        if ( mode.prune ) {
+        // if ( mode.prune ) {
+        // optimization: don't prune for NameExpr since it never has cost
+        if ( mode.prune && !dynamic_cast<const ast::NameExpr *>(expr)) {
                 // trim candidates to single best one
                 PRINT(