Changeset d57e349


Ignore:
Timestamp:
Jun 11, 2019, 1:36:00 PM (2 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
arm-eh, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
3da7c19
Parents:
396037d
Message:

More resolver porting

Location:
src/ResolvExpr
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/AdjustExprType.cc

    r396037d rd57e349  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // AdjustExprType.cc --
     7// AdjustExprType_old.cc --
    88//
    99// Author           : Richard C. Bilson
     
    1414//
    1515
     16#include "AST/Node.hpp"
     17#include "AST/Pass.hpp"
     18#include "AST/SymbolTable.hpp"
     19#include "AST/Type.hpp"
     20#include "AST/TypeEnvironment.hpp"
    1621#include "Common/PassVisitor.h"
    1722#include "SymTab/Indexer.h"       // for Indexer
     
    2227
    2328namespace ResolvExpr {
    24         class AdjustExprType : public WithShortCircuiting {
    25           public:
    26                 AdjustExprType( const TypeEnvironment & env, const SymTab::Indexer & indexer );
     29
     30namespace {
     31        class AdjustExprType_old final : public WithShortCircuiting {
     32                public:
     33                AdjustExprType_old( const TypeEnvironment & env, const SymTab::Indexer & indexer );
    2734                void premutate( VoidType * ) { visit_children = false; }
    2835                void premutate( BasicType * ) { visit_children = false; }
     
    4451                Type * postmutate( TypeInstType *aggregateUseType );
    4552
    46           private:
     53                private:
    4754                const TypeEnvironment & env;
    4855                const SymTab::Indexer & indexer;
    4956        };
    5057
    51         void adjustExprType( Type *&type, const TypeEnvironment &env, const SymTab::Indexer &indexer ) {
    52                 PassVisitor<AdjustExprType> adjuster( env, indexer );
    53                 Type *newType = type->acceptMutator( adjuster );
    54                 type = newType;
    55         }
    56 
    57         void adjustExprType( Type *& type ) {
    58                 TypeEnvironment env;
    59                 SymTab::Indexer indexer;
    60                 adjustExprType( type, env, indexer );
    61         }
    62 
    63         AdjustExprType::AdjustExprType( const TypeEnvironment &env, const SymTab::Indexer &indexer )
     58        AdjustExprType_old::AdjustExprType_old( const TypeEnvironment &env, const SymTab::Indexer &indexer )
    6459                : env( env ), indexer( indexer ) {
    6560        }
    6661
    67         Type * AdjustExprType::postmutate( ArrayType * arrayType ) {
     62        Type * AdjustExprType_old::postmutate( ArrayType * arrayType ) {
    6863                PointerType *pointerType = new PointerType{ arrayType->get_qualifiers(), arrayType->base };
    6964                arrayType->base = nullptr;
     
    7267        }
    7368
    74         Type * AdjustExprType::postmutate( FunctionType * functionType ) {
     69        Type * AdjustExprType_old::postmutate( FunctionType * functionType ) {
    7570                return new PointerType{ Type::Qualifiers(), functionType };
    7671        }
    7772
    78         Type * AdjustExprType::postmutate( TypeInstType * typeInst ) {
     73        Type * AdjustExprType_old::postmutate( TypeInstType * typeInst ) {
    7974                if ( const EqvClass* eqvClass = env.lookup( typeInst->get_name() ) ) {
    8075                        if ( eqvClass->data.kind == TypeDecl::Ftype ) {
     
    9085                return typeInst;
    9186        }
     87} // anonymous namespace
     88
     89void adjustExprType( Type *&type, const TypeEnvironment &env, const SymTab::Indexer &indexer ) {
     90        PassVisitor<AdjustExprType_old> adjuster( env, indexer );
     91        Type *newType = type->acceptMutator( adjuster );
     92        type = newType;
     93}
     94
     95void adjustExprType( Type *& type ) {
     96        TypeEnvironment env;
     97        SymTab::Indexer indexer;
     98        adjustExprType( type, env, indexer );
     99}
     100
     101namespace {
     102        struct AdjustExprType_new final : public ast::WithShortCircuiting {
     103                const ast::TypeEnvironment & tenv;
     104                const ast::SymbolTable & symtab;
     105
     106                AdjustExprType_new( const ast::TypeEnvironment & e, const ast::SymbolTable & syms )
     107                : tenv( e ), symtab( syms ) {}
     108
     109                void premutate( const ast::VoidType * ) { visit_children = false; }
     110                void premutate( const ast::BasicType * ) { visit_children = false; }
     111                void premutate( const ast::PointerType * ) { visit_children = false; }
     112                void premutate( const ast::ArrayType * ) { visit_children = false; }
     113                void premutate( const ast::FunctionType * ) { visit_children = false; }
     114                void premutate( const ast::StructInstType * ) { visit_children = false; }
     115                void premutate( const ast::UnionInstType * ) { visit_children = false; }
     116                void premutate( const ast::EnumInstType * ) { visit_children = false; }
     117                void premutate( const ast::TraitInstType * ) { visit_children = false; }
     118                void premutate( const ast::TypeInstType * ) { visit_children = false; }
     119                void premutate( const ast::TupleType * ) { visit_children = false; }
     120                void premutate( const ast::VarArgsType * ) { visit_children = false; }
     121                void premutate( const ast::ZeroType * ) { visit_children = false; }
     122                void premutate( const ast::OneType * ) { visit_children = false; }
     123
     124                const ast::Type * postmutate( const ast::ArrayType * at ) {
     125                        return new ast::PointerType{ at->base, at->qualifiers };
     126                }
     127
     128                const ast::Type * postmutate( const ast::FunctionType * ft ) {
     129                        return new ast::PointerType{ ft };
     130                }
     131
     132                const ast::Type * postmutate( const ast::TypeInstType * inst ) {
     133                        // replace known function-type-variables with pointer-to-function
     134                        if ( const ast::EqvClass * eqvClass = tenv.lookup( inst->name ) ) {
     135                                if ( eqvClass->data.kind == ast::TypeVar::Ftype ) {
     136                                        return new ast::PointerType{ inst };
     137                                }
     138                        } else if ( const ast::NamedTypeDecl * ntDecl = symtab.lookupType( inst->name ) ) {
     139                                if ( auto tyDecl = dynamic_cast< const ast::TypeDecl * >( ntDecl ) ) {
     140                                        if ( tyDecl->kind == ast::TypeVar::Ftype ) {
     141                                                return new ast::PointerType{ inst };
     142                                        }
     143                                }
     144                        }
     145                        return inst;
     146                }
     147        };
     148} // anonymous namespace
     149
     150const ast::Type * adjustExprType(
     151        const ast::Type * type, const ast::TypeEnvironment & env, const ast::SymbolTable & symtab
     152) {
     153        ast::Pass<AdjustExprType_new> adjuster{ env, symtab };
     154        return type->accept( adjuster );
     155}
     156
    92157} // namespace ResolvExpr
    93158
  • src/ResolvExpr/Candidate.hpp

    r396037d rd57e349  
    4242        ast::OpenVarSet open;      ///< Open variables for environment
    4343        ast::AssertionList need;   ///< Assertions which need to be resolved
     44
     45        Candidate() = default;
    4446};
    4547
     
    4951/// List of candidates
    5052using CandidateList = std::vector< CandidateRef >;
     53
     54/// Holdover behaviour from old `findMinCost` -- xxx -- can maybe be eliminated?
     55static inline void promoteCvtCost( CandidateList & candidates ) {
     56        for ( CandidateRef & r : candidates ) {
     57                r->cost = r->cvtCost;
     58        }
     59}
    5160
    5261void print( std::ostream & os, const Candidate & cand, Indenter indent = {} );
  • src/ResolvExpr/CandidateFinder.cpp

    r396037d rd57e349  
    1717
    1818#include <sstream>
     19#include <string>
     20#include <unordered_map>
    1921
    2022#include "Candidate.hpp"
    2123#include "CompilationState.h"
     24#include "Cost.h"
     25#include "Resolver.h"
    2226#include "SatisfyAssertions.hpp"
     27#include "typeops.h"              // for adjustExprType
    2328#include "AST/Expr.hpp"
    2429#include "AST/Node.hpp"
    2530#include "AST/Pass.hpp"
     31#include "AST/Print.hpp"
     32#include "SymTab/Mangler.h"
    2633
    2734#define PRINT( text ) if ( resolvep ) { text }
     
    4956        /// return type. Skips ambiguous candidates.
    5057        CandidateList pruneCandidates( CandidateList & candidates ) {
    51                 #warning unimplemented
    52                 (void)candidates;
    53                 assert(false);
    54                 return {};
     58                struct PruneStruct {
     59                        CandidateRef candidate;
     60                        bool ambiguous;
     61
     62                        PruneStruct() = default;
     63                        PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
     64                };
     65
     66                // find lowest-cost candidate for each type
     67                std::unordered_map< std::string, PruneStruct > selected;
     68                for ( CandidateRef & candidate : candidates ) {
     69                        std::string mangleName;
     70                        {
     71                                ast::ptr< ast::Type > newType = candidate->expr->result;
     72                                candidate->env.apply( newType );
     73                                mangleName = Mangle::mangle( newType );
     74                        }
     75
     76                        auto found = selected.find( mangleName );
     77                        if ( found != selected.end() ) {
     78                                if ( candidate->cost < found->second.candidate->cost ) {
     79                                        PRINT(
     80                                                std::cerr << "cost " << candidate->cost << " beats "
     81                                                        << found->second.candidate->cost << std::endl;
     82                                        )
     83
     84                                        found->second = PruneStruct{ candidate };
     85                                } else if ( candidate->cost == found->second.candidate->cost ) {
     86                                        // if one of the candidates contains a deleted identifier, can pick the other,
     87                                        // since deleted expressions should not be ambiguous if there is another option
     88                                        // that is at least as good
     89                                        if ( findDeletedExpr( candidate->expr ) ) {
     90                                                // do nothing
     91                                                PRINT( std::cerr << "candidate is deleted" << std::endl; )
     92                                        } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
     93                                                PRINT( std::cerr << "current is deleted" << std::endl; )
     94                                                found->second = PruneStruct{ candidate };
     95                                        } else {
     96                                                PRINT( std::cerr << "marking ambiguous" << std::endl; )
     97                                                found->second.ambiguous = true;
     98                                        }
     99                                } else {
     100                                        PRINT(
     101                                                std::cerr << "cost " << candidate->cost << " loses to "
     102                                                        << found->second.candidate->cost << std::endl;
     103                                        )
     104                                }
     105                        } else {
     106                                selected.emplace_hint( found, mangleName, candidate );
     107                        }
     108                }
     109
     110                // report unambiguous min-cost candidates
     111                CandidateList out;
     112                for ( auto & target : selected ) {
     113                        if ( target.second.ambiguous ) continue;
     114
     115                        CandidateRef cand = target.second.candidate;
     116                       
     117                        ast::ptr< ast::Type > newResult = cand->expr->result;
     118                        cand->env.applyFree( newResult );
     119                        cand->expr = ast::mutate_field(
     120                                cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
     121                       
     122                        out.emplace_back( cand );
     123                }
     124                return out;
     125        }
     126
     127        /// Returns a list of alternatives with the minimum cost in the given list
     128        CandidateList findMinCost( const CandidateList & candidates ) {
     129                CandidateList out;
     130                Cost minCost = Cost::infinity;
     131                for ( const CandidateRef & r : candidates ) {
     132                        if ( r->cost < minCost ) {
     133                                minCost = r->cost;
     134                                out.clear();
     135                                out.emplace_back( r );
     136                        } else if ( r->cost == minCost ) {
     137                                out.emplace_back( r );
     138                        }
     139                }
     140                return out;
    55141        }
    56142
     
    91177        if ( mode.prune ) {
    92178                // trim candidates to single best one
    93                 auto oldsize = candidates.size();
    94179                PRINT(
    95180                        std::cerr << "alternatives before prune:" << std::endl;
     
    98183
    99184                CandidateList pruned = pruneCandidates( candidates );
     185               
    100186                if ( mode.failFast && pruned.empty() ) {
    101187                        std::ostringstream stream;
    102                         CandidateList winners;
    103                        
    104                         #warning unimplemented
    105                         assert(false);
    106                 }
    107         }
    108 
    109         #warning unimplemented
    110         assert(false);
     188                        CandidateList winners = findMinCost( candidates );
     189                        stream << "Cannot choose between " << winners.size() << " alternatives for "
     190                                "expression\n";
     191                        ast::print( stream, expr );
     192                        stream << " Alternatives are:\n";
     193                        print( stream, winners, 1 );
     194                        SemanticError( expr->location, stream.str() );
     195                }
     196
     197                auto oldsize = candidates.size();
     198                candidates = std::move( pruned );
     199
     200                PRINT(
     201                        std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
     202                )
     203                PRINT(
     204                        std::cerr << "there are " << candidates.size() << " alternatives after elimination"
     205                                << std::endl;
     206                )
     207        }
     208
     209        // adjust types after pruning so that types substituted by pruneAlternatives are correctly
     210        // adjusted
     211        if ( mode.adjust ) {
     212                for ( CandidateRef & r : candidates ) {
     213                        r->expr = ast::mutate_field(
     214                                r->expr.get(), &ast::Expr::result,
     215                                adjustExprType( r->expr->result, r->env, symtab ) );
     216                }
     217        }
     218
     219        // Central location to handle gcc extension keyword, etc. for all expressions
     220        for ( CandidateRef & r : candidates ) {
     221                if ( r->expr->extension != expr->extension ) {
     222                        r->expr.get_and_mutate()->extension = expr->extension;
     223                }
     224        }
    111225}
    112226
  • src/ResolvExpr/Resolver.cc

    r396037d rd57e349  
    957957                        }
    958958                };
    959 
    960                 /// Check if this expression is or includes a deleted expression
    961                 const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr ) {
    962                         ast::Pass<DeleteFinder_new> finder;
    963                         expr->accept( finder );
    964                         return finder.pass.delExpr;
    965                 }
    966 
     959        } // anonymous namespace
     960
     961        /// Check if this expression is or includes a deleted expression
     962        const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr ) {
     963                ast::Pass<DeleteFinder_new> finder;
     964                expr->accept( finder );
     965                return finder.pass.delExpr;
     966        }
     967
     968        namespace {
    967969                /// always-accept candidate filter
    968970                bool anyCandidate( const Candidate & ) { return true; }
     
    10241026
    10251027                        // promote candidate.cvtCost to .cost
    1026                         for ( CandidateRef & cand : winners ) {
    1027                                 cand->cost = cand->cvtCost;
    1028                         }
     1028                        promoteCvtCost( winners );
    10291029
    10301030                        // produce ambiguous errors, if applicable
  • src/ResolvExpr/Resolver.h

    r396037d rd57e349  
    2929namespace ast {
    3030        class Decl;
     31        class DeletedExpr;
    3132} // namespace ast
    3233
     
    4849        /// Checks types and binds syntactic constructs to typed representations
    4950        void resolve( std::list< ast::ptr<ast::Decl> >& translationUnit );
     51        /// Searches expr and returns the first DeletedExpr found, otherwise nullptr
     52        const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr );
    5053} // namespace ResolvExpr
    5154
  • src/ResolvExpr/typeops.h

    r396037d rd57e349  
    7171                } // while
    7272        }
     73
     74        /// Replaces array types with equivalent pointer, and function types with a pointer-to-function
     75        const ast::Type * adjustExprType(
     76                const ast::Type * type, const ast::TypeEnvironment & env, const ast::SymbolTable & symtab );
    7377
    7478        // in CastCost.cc
Note: See TracChangeset for help on using the changeset viewer.