Changeset d57e349 for src/ResolvExpr

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

Location:

src/ResolvExpr

Files:

• AdjustExprType.cc (modified) (6 diffs)
• Candidate.hpp (modified) (2 diffs)
• CandidateFinder.cpp (modified) (4 diffs)
• Resolver.cc (modified) (2 diffs)
• Resolver.h (modified) (2 diffs)
• typeops.h (modified) (1 diff)

src/ResolvExpr/AdjustExprType.cc

@@ -5 +5 @@
 // file "LICENCE" distributed with Cforall.
 //
-// AdjustExprType.cc --
+// AdjustExprType_old.cc --
 //
 // Author           : Richard C. Bilson
@@ -14 +14 @@
 //
 
+#include "AST/Node.hpp"
+#include "AST/Pass.hpp"
+#include "AST/SymbolTable.hpp"
+#include "AST/Type.hpp"
+#include "AST/TypeEnvironment.hpp"
 #include "Common/PassVisitor.h"
 #include "SymTab/Indexer.h"       // for Indexer
@@ -22 +27 @@
 
 namespace ResolvExpr {
-        class AdjustExprType : public WithShortCircuiting {
-          public:
-                AdjustExprType( const TypeEnvironment & env, const SymTab::Indexer & indexer );
+
+namespace {
+        class AdjustExprType_old final : public WithShortCircuiting {
+                public:
+                AdjustExprType_old( const TypeEnvironment & env, const SymTab::Indexer & indexer );
                 void premutate( VoidType * ) { visit_children = false; }
                 void premutate( BasicType * ) { visit_children = false; }
@@ -44 +51 @@
                 Type * postmutate( TypeInstType *aggregateUseType );
 
-          private:
+                private:
                 const TypeEnvironment & env;
                 const SymTab::Indexer & indexer;
         };
 
-        void adjustExprType( Type *&type, const TypeEnvironment &env, const SymTab::Indexer &indexer ) {
-                PassVisitor<AdjustExprType> adjuster( env, indexer );
-                Type *newType = type->acceptMutator( adjuster );
-                type = newType;
-        }
-
-        void adjustExprType( Type *& type ) {
-                TypeEnvironment env;
-                SymTab::Indexer indexer;
-                adjustExprType( type, env, indexer );
-        }
-
-        AdjustExprType::AdjustExprType( const TypeEnvironment &env, const SymTab::Indexer &indexer )
+        AdjustExprType_old::AdjustExprType_old( const TypeEnvironment &env, const SymTab::Indexer &indexer )
                 : env( env ), indexer( indexer ) {
         }
 
-        Type * AdjustExprType::postmutate( ArrayType * arrayType ) {
+        Type * AdjustExprType_old::postmutate( ArrayType * arrayType ) {
                 PointerType *pointerType = new PointerType{ arrayType->get_qualifiers(), arrayType->base };
                 arrayType->base = nullptr;
@@ -72 +67 @@
         }
 
-        Type * AdjustExprType::postmutate( FunctionType * functionType ) {
+        Type * AdjustExprType_old::postmutate( FunctionType * functionType ) {
                 return new PointerType{ Type::Qualifiers(), functionType };
         }
 
-        Type * AdjustExprType::postmutate( TypeInstType * typeInst ) {
+        Type * AdjustExprType_old::postmutate( TypeInstType * typeInst ) {
                 if ( const EqvClass* eqvClass = env.lookup( typeInst->get_name() ) ) {
                         if ( eqvClass->data.kind == TypeDecl::Ftype ) {
@@ -90 +85 @@
                 return typeInst;
         }
+} // anonymous namespace
+
+void adjustExprType( Type *&type, const TypeEnvironment &env, const SymTab::Indexer &indexer ) {
+        PassVisitor<AdjustExprType_old> adjuster( env, indexer );
+        Type *newType = type->acceptMutator( adjuster );
+        type = newType;
+}
+
+void adjustExprType( Type *& type ) {
+        TypeEnvironment env;
+        SymTab::Indexer indexer;
+        adjustExprType( type, env, indexer );
+}
+
+namespace {
+        struct AdjustExprType_new final : public ast::WithShortCircuiting {
+                const ast::TypeEnvironment & tenv;
+                const ast::SymbolTable & symtab;
+
+                AdjustExprType_new( const ast::TypeEnvironment & e, const ast::SymbolTable & syms )
+                : tenv( e ), symtab( syms ) {}
+
+                void premutate( const ast::VoidType * ) { visit_children = false; }
+                void premutate( const ast::BasicType * ) { visit_children = false; }
+                void premutate( const ast::PointerType * ) { visit_children = false; }
+                void premutate( const ast::ArrayType * ) { visit_children = false; }
+                void premutate( const ast::FunctionType * ) { visit_children = false; }
+                void premutate( const ast::StructInstType * ) { visit_children = false; }
+                void premutate( const ast::UnionInstType * ) { visit_children = false; }
+                void premutate( const ast::EnumInstType * ) { visit_children = false; }
+                void premutate( const ast::TraitInstType * ) { visit_children = false; }
+                void premutate( const ast::TypeInstType * ) { visit_children = false; }
+                void premutate( const ast::TupleType * ) { visit_children = false; }
+                void premutate( const ast::VarArgsType * ) { visit_children = false; }
+                void premutate( const ast::ZeroType * ) { visit_children = false; }
+                void premutate( const ast::OneType * ) { visit_children = false; }
+
+                const ast::Type * postmutate( const ast::ArrayType * at ) {
+                        return new ast::PointerType{ at->base, at->qualifiers };
+                }
+
+                const ast::Type * postmutate( const ast::FunctionType * ft ) {
+                        return new ast::PointerType{ ft };
+                }
+
+                const ast::Type * postmutate( const ast::TypeInstType * inst ) {
+                        // replace known function-type-variables with pointer-to-function
+                        if ( const ast::EqvClass * eqvClass = tenv.lookup( inst->name ) ) {
+                                if ( eqvClass->data.kind == ast::TypeVar::Ftype ) {
+                                        return new ast::PointerType{ inst };
+                                }
+                        } else if ( const ast::NamedTypeDecl * ntDecl = symtab.lookupType( inst->name ) ) {
+                                if ( auto tyDecl = dynamic_cast< const ast::TypeDecl * >( ntDecl ) ) {
+                                        if ( tyDecl->kind == ast::TypeVar::Ftype ) {
+                                                return new ast::PointerType{ inst };
+                                        }
+                                }
+                        }
+                        return inst;
+                }
+        };
+} // anonymous namespace
+
+const ast::Type * adjustExprType( 
+        const ast::Type * type, const ast::TypeEnvironment & env, const ast::SymbolTable & symtab 
+) {
+        ast::Pass<AdjustExprType_new> adjuster{ env, symtab };
+        return type->accept( adjuster );
+}
+
 } // namespace ResolvExpr
 

src/ResolvExpr/Candidate.hpp

@@ -42 +42 @@
         ast::OpenVarSet open;      ///< Open variables for environment
         ast::AssertionList need;   ///< Assertions which need to be resolved
+
+        Candidate() = default;
 };
 
@@ -49 +51 @@
 /// List of candidates
 using CandidateList = std::vector< CandidateRef >;
+
+/// Holdover behaviour from old `findMinCost` -- xxx -- can maybe be eliminated?
+static inline void promoteCvtCost( CandidateList & candidates ) {
+        for ( CandidateRef & r : candidates ) {
+                r->cost = r->cvtCost;
+        }
+}
 
 void print( std::ostream & os, const Candidate & cand, Indenter indent = {} );

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;
+                }
+        }
 }
 

src/ResolvExpr/Resolver.cc

@@ -957 +957 @@
                         }
                 };
-
-                /// Check if this expression is or includes a deleted expression
-                const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr ) {
-                        ast::Pass<DeleteFinder_new> finder;
-                        expr->accept( finder );
-                        return finder.pass.delExpr;
-                }
-
+        } // anonymous namespace
+
+        /// Check if this expression is or includes a deleted expression
+        const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr ) {
+                ast::Pass<DeleteFinder_new> finder;
+                expr->accept( finder );
+                return finder.pass.delExpr;
+        }
+
+        namespace {
                 /// always-accept candidate filter
                 bool anyCandidate( const Candidate & ) { return true; }
@@ -1024 +1026 @@
 
                         // promote candidate.cvtCost to .cost
-                        for ( CandidateRef & cand : winners ) {
-                                cand->cost = cand->cvtCost;
-                        }
+                        promoteCvtCost( winners );
 
                         // produce ambiguous errors, if applicable

src/ResolvExpr/Resolver.h

@@ -29 +29 @@
 namespace ast {
         class Decl;
+        class DeletedExpr;
 } // namespace ast
 
@@ -48 +49 @@
         /// Checks types and binds syntactic constructs to typed representations
         void resolve( std::list< ast::ptr<ast::Decl> >& translationUnit );
+        /// Searches expr and returns the first DeletedExpr found, otherwise nullptr
+        const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr );
 } // namespace ResolvExpr
 

src/ResolvExpr/typeops.h

@@ -71 +71 @@
                 } // while
         }
+
+        /// Replaces array types with equivalent pointer, and function types with a pointer-to-function
+        const ast::Type * adjustExprType( 
+                const ast::Type * type, const ast::TypeEnvironment & env, const ast::SymbolTable & symtab );
 
         // in CastCost.cc