Index: src/ResolvExpr/AdjustExprType.cc =================================================================== --- src/ResolvExpr/AdjustExprType.cc (revision 396037da5f2f734f97de7b80432deea29f7ed2b8) +++ src/ResolvExpr/AdjustExprType.cc (revision d57e349b59b2caa4153e307659633985bc70b2c4) @@ -5,5 +5,5 @@ // file "LICENCE" distributed with Cforall. // -// AdjustExprType.cc -- +// AdjustExprType_old.cc -- // // Author : Richard C. Bilson @@ -14,4 +14,9 @@ // +#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,7 +27,9 @@ 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,26 +51,14 @@ 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 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,9 +67,9 @@ } - 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,4 +85,74 @@ return typeInst; } +} // anonymous namespace + +void adjustExprType( Type *&type, const TypeEnvironment &env, const SymTab::Indexer &indexer ) { + PassVisitor 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 adjuster{ env, symtab }; + return type->accept( adjuster ); +} + } // namespace ResolvExpr Index: src/ResolvExpr/Candidate.hpp =================================================================== --- src/ResolvExpr/Candidate.hpp (revision 396037da5f2f734f97de7b80432deea29f7ed2b8) +++ src/ResolvExpr/Candidate.hpp (revision d57e349b59b2caa4153e307659633985bc70b2c4) @@ -42,4 +42,6 @@ ast::OpenVarSet open; ///< Open variables for environment ast::AssertionList need; ///< Assertions which need to be resolved + + Candidate() = default; }; @@ -49,4 +51,11 @@ /// 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 = {} ); Index: src/ResolvExpr/CandidateFinder.cpp =================================================================== --- src/ResolvExpr/CandidateFinder.cpp (revision 396037da5f2f734f97de7b80432deea29f7ed2b8) +++ src/ResolvExpr/CandidateFinder.cpp (revision d57e349b59b2caa4153e307659633985bc70b2c4) @@ -17,11 +17,18 @@ #include +#include +#include #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,8 +56,87 @@ /// 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,5 +177,4 @@ if ( mode.prune ) { // trim candidates to single best one - auto oldsize = candidates.size(); PRINT( std::cerr << "alternatives before prune:" << std::endl; @@ -98,15 +183,44 @@ 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; + } + } } Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 396037da5f2f734f97de7b80432deea29f7ed2b8) +++ src/ResolvExpr/Resolver.cc (revision d57e349b59b2caa4153e307659633985bc70b2c4) @@ -957,12 +957,14 @@ } }; - - /// Check if this expression is or includes a deleted expression - const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr ) { - ast::Pass 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 finder; + expr->accept( finder ); + return finder.pass.delExpr; + } + + namespace { /// always-accept candidate filter bool anyCandidate( const Candidate & ) { return true; } @@ -1024,7 +1026,5 @@ // promote candidate.cvtCost to .cost - for ( CandidateRef & cand : winners ) { - cand->cost = cand->cvtCost; - } + promoteCvtCost( winners ); // produce ambiguous errors, if applicable Index: src/ResolvExpr/Resolver.h =================================================================== --- src/ResolvExpr/Resolver.h (revision 396037da5f2f734f97de7b80432deea29f7ed2b8) +++ src/ResolvExpr/Resolver.h (revision d57e349b59b2caa4153e307659633985bc70b2c4) @@ -29,4 +29,5 @@ namespace ast { class Decl; + class DeletedExpr; } // namespace ast @@ -48,4 +49,6 @@ /// Checks types and binds syntactic constructs to typed representations void resolve( std::list< ast::ptr >& translationUnit ); + /// Searches expr and returns the first DeletedExpr found, otherwise nullptr + const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr ); } // namespace ResolvExpr Index: src/ResolvExpr/typeops.h =================================================================== --- src/ResolvExpr/typeops.h (revision 396037da5f2f734f97de7b80432deea29f7ed2b8) +++ src/ResolvExpr/typeops.h (revision d57e349b59b2caa4153e307659633985bc70b2c4) @@ -71,4 +71,8 @@ } // 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