Changeset 4b7cce6


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

Fill in CandidateFinder? boilerplate in resolver port

Location:
src/ResolvExpr
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/AlternativeFinder.cc

    r3da7c19 r4b7cce6  
    2929#include "AlternativeFinder.h"
    3030#include "AST/Expr.hpp"
     31#include "AST/SymbolTable.hpp"
    3132#include "AST/Type.hpp"
    3233#include "Common/SemanticError.h"  // for SemanticError
  • src/ResolvExpr/Candidate.hpp

    r3da7c19 r4b7cce6  
    3030        /// A list of unresolved assertions
    3131        using AssertionList = std::vector<AssertionSet::value_type>;
     32
     33        /// Convenience to merge AssertionList into AssertionSet
     34        static inline void mergeAssertionSet( AssertionSet & dst, const AssertionList & src ) {
     35                for ( const auto & s : src ) { dst.emplace( s ); }
     36        }
    3237}
    3338
     
    4348        ast::AssertionList need;   ///< Assertions which need to be resolved
    4449
    45         Candidate() = default;
     50        Candidate() : expr(), cost( Cost::zero ), cvtCost( Cost::zero ), env(), open(), need() {}
     51       
     52        Candidate( const ast::Expr * x, const ast::TypeEnvironment & e )
     53        : expr( x ), cost( Cost::zero ), cvtCost( Cost::zero ), env( e ), open(), need() {}
     54
     55        Candidate( const Candidate & o, const ast::Expr * x )
     56        : expr( x ), cost( o.cost ), cvtCost( Cost::zero ), env( o.env ), open( o.open ),
     57          need( o.need ) {}
     58       
     59        Candidate(
     60                const ast::Expr * x, ast::TypeEnvironment && e, ast::OpenVarSet && o,
     61                ast::AssertionSet && n, const Cost & c )
     62        : expr( x ), cost( c ), cvtCost( Cost::zero ), env( std::move( e ) ), open( std::move( o ) ),
     63          need( n.begin(), n.end() ) {}
    4664};
    4765
     
    5169/// List of candidates
    5270using CandidateList = std::vector< CandidateRef >;
     71
     72/// Sum the cost of a list of candidates
     73static inline Cost sumCost( const CandidateList & candidates ) {
     74        Cost total = Cost::zero;
     75        for ( const CandidateRef & r : candidates ) { total += r->cost; }
     76        return total;
     77}
    5378
    5479/// Holdover behaviour from old `findMinCost` -- xxx -- can maybe be eliminated?
  • src/ResolvExpr/CandidateFinder.cpp

    r3da7c19 r4b7cce6  
    1616#include "CandidateFinder.hpp"
    1717
     18#include <iterator>               // for back_inserter
    1819#include <sstream>
    1920#include <string>
     
    2627#include "SatisfyAssertions.hpp"
    2728#include "typeops.h"              // for adjustExprType
     29#include "Unify.h"
    2830#include "AST/Expr.hpp"
    2931#include "AST/Node.hpp"
    3032#include "AST/Pass.hpp"
    3133#include "AST/Print.hpp"
     34#include "AST/SymbolTable.hpp"
    3235#include "SymTab/Mangler.h"
    3336
     
    3942
    4043        /// Actually visits expressions to find their candidate interpretations
    41         struct Finder {
    42                 CandidateFinder & candFinder;
     44        struct Finder final : public ast::WithShortCircuiting {
     45                CandidateFinder & selfFinder;
    4346                const ast::SymbolTable & symtab;
    4447                CandidateList & candidates;
     
    4750
    4851                Finder( CandidateFinder & f )
    49                 : candFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ),
     52                : selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ),
    5053                  targetType( f.targetType ) {}
    5154               
    52                 #warning unimplemented
     55                void previsit( const ast::Node * ) { visit_children = false; }
     56
     57                /// Convenience to add candidate to list
     58                template<typename... Args>
     59                void addCandidate( Args &&... args ) {
     60                        candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
     61                }
     62
     63                void postvisit( const ast::ApplicationExpr * applicationExpr ) {
     64                        addCandidate( applicationExpr, tenv );
     65                }
     66
     67                void postvisit( const ast::UntypedExpr * untypedExpr ) {
     68                        #warning unimplemented
     69                        (void)untypedExpr;
     70                        assert(false);
     71                }
     72
     73                /// true if expression is an lvalue
     74                static bool isLvalue( const ast::Expr * x ) {
     75                        return x->result && ( x->result->is_lvalue() || x->result.as< ast::ReferenceType >() );
     76                }
     77
     78                void postvisit( const ast::AddressExpr * addressExpr ) {
     79                        CandidateFinder finder{ symtab, tenv };
     80                        finder.find( addressExpr->arg );
     81                        for ( CandidateRef & r : finder.candidates ) {
     82                                if ( ! isLvalue( r->expr ) ) continue;
     83                                addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
     84                        }
     85                }
     86
     87                void postvisit( const ast::LabelAddressExpr * labelExpr ) {
     88                        addCandidate( labelExpr, tenv );
     89                }
     90
     91                void postvisit( const ast::CastExpr * castExpr ) {
     92                        #warning unimplemented
     93                        (void)castExpr;
     94                        assert(false);
     95                }
     96
     97                void postvisit( const ast::VirtualCastExpr * castExpr ) {
     98                        assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
     99                        CandidateFinder finder{ symtab, tenv };
     100                        // don't prune here, all alternatives guaranteed to have same type
     101                        finder.find( castExpr->arg, ResolvMode::withoutPrune() );
     102                        for ( CandidateRef & r : finder.candidates ) {
     103                                addCandidate(
     104                                        *r, new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
     105                        }
     106                }
     107
     108                void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
     109                        #warning unimplemented
     110                        (void)memberExpr;
     111                        assert(false);
     112                }
     113
     114                void postvisit( const ast::MemberExpr * memberExpr ) {
     115                        addCandidate( memberExpr, tenv );
     116                }
     117
     118                void postvisit( const ast::NameExpr * variableExpr ) {
     119                        #warning unimplemented
     120                        (void)variableExpr;
     121                        assert(false);
     122                }
     123
     124                void postvisit( const ast::VariableExpr * variableExpr ) {
     125                        // not sufficient to just pass `variableExpr` here, type might have changed since
     126                        // creation
     127                        addCandidate(
     128                                new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
     129                }
     130
     131                void postvisit( const ast::ConstantExpr * constantExpr ) {
     132                        addCandidate( constantExpr, tenv );
     133                }
     134
     135                void postvisit( const ast::SizeofExpr * sizeofExpr ) {
     136                        #warning unimplemented
     137                        (void)sizeofExpr;
     138                        assert(false);
     139                }
     140
     141                void postvisit( const ast::AlignofExpr * alignofExpr ) {
     142                        #warning unimplemented
     143                        (void)alignofExpr;
     144                        assert(false);
     145                }
     146
     147                void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
     148                        #warning unimplemented
     149                        (void)offsetofExpr;
     150                        assert(false);
     151                }
     152
     153                void postvisit( const ast::OffsetofExpr * offsetofExpr ) {
     154                        addCandidate( offsetofExpr, tenv );
     155                }
     156
     157                void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
     158                        addCandidate( offsetPackExpr, tenv );
     159                }
     160
     161                void postvisit( const ast::LogicalExpr * logicalExpr ) {
     162                        CandidateFinder finder1{ symtab, tenv };
     163                        finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
     164                        if ( finder1.candidates.empty() ) return;
     165
     166                        CandidateFinder finder2{ symtab, tenv };
     167                        finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
     168                        if ( finder2.candidates.empty() ) return;
     169
     170                        for ( const CandidateRef & r1 : finder1.candidates ) {
     171                                for ( const CandidateRef & r2 : finder2.candidates ) {
     172                                        ast::TypeEnvironment env{ r1->env };
     173                                        env.simpleCombine( r2->env );
     174                                        ast::OpenVarSet open{ r1->open };
     175                                        mergeOpenVars( open, r2->open );
     176                                        ast::AssertionSet need;
     177                                        mergeAssertionSet( need, r1->need );
     178                                        mergeAssertionSet( need, r2->need );
     179
     180                                        addCandidate(
     181                                                new ast::LogicalExpr{
     182                                                        logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
     183                                                std::move( env ), std::move( open ), std::move( need ),
     184                                                r1->cost + r2->cost );
     185                                }
     186                        }
     187                }
     188
     189                void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
     190                        // candidates for condition
     191                        CandidateFinder finder1{ symtab, tenv };
     192                        finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
     193                        if ( finder1.candidates.empty() ) return;
     194
     195                        // candidates for true result
     196                        CandidateFinder finder2{ symtab, tenv };
     197                        finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
     198                        if ( finder2.candidates.empty() ) return;
     199
     200                        // candidates for false result
     201                        CandidateFinder finder3{ symtab, tenv };
     202                        finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
     203                        if ( finder3.candidates.empty() ) return;
     204
     205                        for ( const CandidateRef & r1 : finder1.candidates ) {
     206                                for ( const CandidateRef & r2 : finder2.candidates ) {
     207                                        for ( const CandidateRef & r3 : finder3.candidates ) {
     208                                                ast::TypeEnvironment env{ r1->env };
     209                                                env.simpleCombine( r2->env );
     210                                                env.simpleCombine( r3->env );
     211                                                ast::OpenVarSet open{ r1->open };
     212                                                mergeOpenVars( open, r2->open );
     213                                                mergeOpenVars( open, r3->open );
     214                                                ast::AssertionSet need;
     215                                                mergeAssertionSet( need, r1->need );
     216                                                mergeAssertionSet( need, r2->need );
     217                                                mergeAssertionSet( need, r3->need );
     218                                                ast::AssertionSet have;
     219
     220                                                // unify true and false results, then infer parameters to produce new
     221                                                // candidates
     222                                                ast::ptr< ast::Type > common;
     223                                                if (
     224                                                        unify(
     225                                                                r2->expr->result, r3->expr->result, env, need, have, open, symtab,
     226                                                                common )
     227                                                ) {
     228                                                        #warning unimplemented
     229                                                        assert(false);
     230                                                }
     231                                        }
     232                                }
     233                        }
     234                }
     235
     236                void postvisit( const ast::CommaExpr * commaExpr ) {
     237                        ast::TypeEnvironment env{ tenv };
     238                        ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env );
     239                       
     240                        CandidateFinder finder2{ symtab, env };
     241                        finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
     242
     243                        for ( const CandidateRef & r2 : finder2.candidates ) {
     244                                addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
     245                        }
     246                }
     247
     248                void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
     249                        addCandidate( ctorExpr, tenv );
     250                }
     251
     252                void postvisit( const ast::ConstructorExpr * ctorExpr ) {
     253                        CandidateFinder finder{ symtab, tenv };
     254                        finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
     255                        for ( CandidateRef & r : finder.candidates ) {
     256                                addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
     257                        }
     258                }
     259
     260                void postvisit( const ast::RangeExpr * rangeExpr ) {
     261                        // resolve low and high, accept candidates where low and high types unify
     262                        CandidateFinder finder1{ symtab, tenv };
     263                        finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
     264                        if ( finder1.candidates.empty() ) return;
     265
     266                        CandidateFinder finder2{ symtab, tenv };
     267                        finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
     268                        if ( finder2.candidates.empty() ) return;
     269
     270                        for ( const CandidateRef & r1 : finder1.candidates ) {
     271                                for ( const CandidateRef & r2 : finder2.candidates ) {
     272                                        ast::TypeEnvironment env{ r1->env };
     273                                        env.simpleCombine( r2->env );
     274                                        ast::OpenVarSet open{ r1->open };
     275                                        mergeOpenVars( open, r2->open );
     276                                        ast::AssertionSet need;
     277                                        mergeAssertionSet( need, r1->need );
     278                                        mergeAssertionSet( need, r2->need );
     279                                        ast::AssertionSet have;
     280
     281                                        ast::ptr< ast::Type > common;
     282                                        if (
     283                                                unify(
     284                                                        r1->expr->result, r2->expr->result, env, need, have, open, symtab,
     285                                                        common )
     286                                        ) {
     287                                                ast::RangeExpr * newExpr =
     288                                                        new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
     289                                                newExpr->result = common ? common : r1->expr->result;
     290                                               
     291                                                #warning unimplemented
     292                                                assert(false);
     293                                        }
     294                                }
     295                        }
     296                }
     297
     298                void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
     299                        std::vector< CandidateFinder > subCandidates =
     300                                selfFinder.findSubExprs( tupleExpr->exprs );
     301                        std::vector< CandidateList > possibilities;
     302                        combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
     303
     304                        for ( const CandidateList & subs : possibilities ) {
     305                                std::vector< ast::ptr< ast::Expr > > exprs;
     306                                exprs.reserve( subs.size() );
     307                                for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
     308
     309                                ast::TypeEnvironment env;
     310                                ast::OpenVarSet open;
     311                                ast::AssertionSet need;
     312                                for ( const CandidateRef & sub : subs ) {
     313                                        env.simpleCombine( sub->env );
     314                                        mergeOpenVars( open, sub->open );
     315                                        mergeAssertionSet( need, sub->need );
     316                                }
     317
     318                                addCandidate(
     319                                        new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },
     320                                        std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
     321                        }
     322                }
     323
     324                void postvisit( const ast::TupleExpr * tupleExpr ) {
     325                        addCandidate( tupleExpr, tenv );
     326                }
     327
     328                void postvisit( const ast::TupleIndexExpr * tupleExpr ) {
     329                        addCandidate( tupleExpr, tenv );
     330                }
     331
     332                void postvisit( const ast::TupleAssignExpr * tupleExpr ) {
     333                        addCandidate( tupleExpr, tenv );
     334                }
     335
     336                void postvisit( const ast::UniqueExpr * unqExpr ) {
     337                        CandidateFinder finder{ symtab, tenv };
     338                        finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
     339                        for ( CandidateRef & r : finder.candidates ) {
     340                                // ensure that the the id is passed on so that the expressions are "linked"
     341                                addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
     342                        }
     343                }
     344
     345                void postvisit( const ast::StmtExpr * stmtExpr ) {
     346                        #warning unimplemented
     347                        (void)stmtExpr;
     348                        assert(false);
     349                }
     350
     351                void postvisit( const ast::UntypedInitExpr * initExpr ) {
     352                        #warning unimplemented
     353                        (void)initExpr;
     354                        assert(false);
     355                }
     356
     357                void postvisit( const ast::InitExpr * ) {
     358                        assertf( false, "CandidateFinder should never see a resolved InitExpr." );
     359                }
     360
     361                void postvisit( const ast::DeletedExpr * ) {
     362                        assertf( false, "CandidateFinder should never see a DeletedExpr." );
     363                }
     364
     365                void postvisit( const ast::GenericExpr * ) {
     366                        assertf( false, "_Generic is not yet supported." );
     367                }
    53368        };
    54369
  • src/ResolvExpr/Resolver.cc

    r3da7c19 r4b7cce6  
    11001100                        StripCasts_new::strip( expr );
    11011101                }
    1102 
    1103                 /// Find the expression candidate that is the unique best match for `untyped` in a `void`
    1104                 /// context.
    1105                 ast::ptr< ast::Expr > resolveInVoidContext(
    1106                         const ast::Expr * expr, const ast::SymbolTable & symtab, ast::TypeEnvironment & env
    1107                 ) {
    1108                         assertf( expr, "expected a non-null expression" );
    1109                        
    1110                         // set up and resolve expression cast to void
    1111                         ast::CastExpr * untyped = new ast::CastExpr{ expr->location, expr };
    1112                         CandidateRef choice = findUnfinishedKindExpression(
    1113                                 untyped, symtab, "", anyCandidate, ResolvMode::withAdjustment() );
    1114                        
    1115                         // a cast expression has either 0 or 1 interpretations (by language rules);
    1116                         // if 0, an exception has already been thrown, and this code will not run
    1117                         const ast::CastExpr * castExpr = choice->expr.strict_as< ast::CastExpr >();
    1118                         env = std::move( choice->env );
    1119 
    1120                         return castExpr->arg;
    1121                 }
    1122 
     1102        } // anonymous namespace
     1103
     1104               
     1105        ast::ptr< ast::Expr > resolveInVoidContext(
     1106                const ast::Expr * expr, const ast::SymbolTable & symtab, ast::TypeEnvironment & env
     1107        ) {
     1108                assertf( expr, "expected a non-null expression" );
     1109               
     1110                // set up and resolve expression cast to void
     1111                ast::CastExpr * untyped = new ast::CastExpr{ expr->location, expr };
     1112                CandidateRef choice = findUnfinishedKindExpression(
     1113                        untyped, symtab, "", anyCandidate, ResolvMode::withAdjustment() );
     1114               
     1115                // a cast expression has either 0 or 1 interpretations (by language rules);
     1116                // if 0, an exception has already been thrown, and this code will not run
     1117                const ast::CastExpr * castExpr = choice->expr.strict_as< ast::CastExpr >();
     1118                env = std::move( choice->env );
     1119
     1120                return castExpr->arg;
     1121        }
     1122
     1123        namespace {
    11231124                /// Resolve `untyped` to the expression whose candidate is the best match for a `void`
    11241125                /// context.
  • src/ResolvExpr/Resolver.h

    r3da7c19 r4b7cce6  
    1717
    1818#include <list>          // for list
    19 #include <AST/Node.hpp>  // for ptr
     19
     20#include "AST/Node.hpp"  // for ptr
    2021
    2122class ConstructorInit;
     
    3031        class Decl;
    3132        class DeletedExpr;
     33        class SymbolTable;
     34        class TypeEnvironment;
    3235} // namespace ast
    3336
     
    5154        /// Searches expr and returns the first DeletedExpr found, otherwise nullptr
    5255        const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr );
     56        /// Find the expression candidate that is the unique best match for `untyped` in a `void`
     57        /// context.
     58        ast::ptr< ast::Expr > resolveInVoidContext(
     59                const ast::Expr * expr, const ast::SymbolTable & symtab, ast::TypeEnvironment & env );
    5360} // namespace ResolvExpr
    5461
Note: See TracChangeset for help on using the changeset viewer.