Changeset d57e349 for src/ResolvExpr/CandidateFinder.cpp

Timestamp:

Jun 11, 2019, 1:36:00 PM (5 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

3da7c19

Parents:

396037d

Message:

More resolver porting

File:

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

src/ResolvExpr/CandidateFinder.cpp

@@ -17 +17 @@
 
 #include <sstream>
+#include <string>
+#include <unordered_map>
 
 #include "Candidate.hpp"
 #include "CompilationState.h"
+#include "Cost.h"
+#include "Resolver.h"
 #include "SatisfyAssertions.hpp"
+#include "typeops.h"              // for adjustExprType
 #include "AST/Expr.hpp"
 #include "AST/Node.hpp"
 #include "AST/Pass.hpp"
+#include "AST/Print.hpp"
+#include "SymTab/Mangler.h"
 
 #define PRINT( text ) if ( resolvep ) { text }
@@ -49 +56 @@
         /// return type. Skips ambiguous candidates.
         CandidateList pruneCandidates( CandidateList & candidates ) {
-                #warning unimplemented
-                (void)candidates;
-                assert(false);
-                return {};
+                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;
+                for ( CandidateRef & candidate : candidates ) {
+                        std::string mangleName;
+                        {
+                                ast::ptr< ast::Type > newType = candidate->expr->result;
+                                candidate->env.apply( newType );
+                                mangleName = Mangle::mangle( newType );
+                        }
+
+                        auto found = selected.find( mangleName );
+                        if ( found != selected.end() ) {
+                                if ( candidate->cost < found->second.candidate->cost ) {
+                                        PRINT(
+                                                std::cerr << "cost " << candidate->cost << " beats " 
+                                                        << found->second.candidate->cost << std::endl;
+                                        )
+
+                                        found->second = PruneStruct{ candidate };
+                                } else if ( candidate->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( candidate->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{ candidate };
+                                        } else {
+                                                PRINT( std::cerr << "marking ambiguous" << std::endl; )
+                                                found->second.ambiguous = true;
+                                        }
+                                } else {
+                                        PRINT(
+                                                std::cerr << "cost " << candidate->cost << " loses to " 
+                                                        << found->second.candidate->cost << std::endl;
+                                        )
+                                }
+                        } else {
+                                selected.emplace_hint( found, mangleName, candidate );
+                        }
+                }
+
+                // 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 );
+                }
+                return out;
+        }
+
+        /// 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;
         }
 
@@ -91 +177 @@
         if ( mode.prune ) {
                 // trim candidates to single best one
-                auto oldsize = candidates.size();
                 PRINT(
                         std::cerr << "alternatives before prune:" << std::endl;
@@ -98 +183 @@
 
                 CandidateList pruned = pruneCandidates( candidates );
+                
                 if ( mode.failFast && pruned.empty() ) {
                         std::ostringstream stream;
-                        CandidateList winners;
-                        
-                        #warning unimplemented
-                        assert(false);
-                }
-        }
-
-        #warning unimplemented
-        assert(false);
+                        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() );
+                }
+
+                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, 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;
+                }
+        }
 }