Changeset 4b7cce6 for src/ResolvExpr

Timestamp:

Jun 11, 2019, 3:42:10 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:

432ce7a

Parents:

3da7c19

Message:

Fill in CandidateFinder? boilerplate in resolver port

Location:

src/ResolvExpr

Files:

• AlternativeFinder.cc (modified) (1 diff)
• Candidate.hpp (modified) (3 diffs)
• CandidateFinder.cpp (modified) (4 diffs)
• Resolver.cc (modified) (1 diff)
• Resolver.h (modified) (3 diffs)

src/ResolvExpr/AlternativeFinder.cc

@@ -29 +29 @@
 #include "AlternativeFinder.h"
 #include "AST/Expr.hpp"
+#include "AST/SymbolTable.hpp"
 #include "AST/Type.hpp"
 #include "Common/SemanticError.h"  // for SemanticError

src/ResolvExpr/Candidate.hpp

@@ -30 +30 @@
         /// A list of unresolved assertions
         using AssertionList = std::vector<AssertionSet::value_type>;
+
+        /// Convenience to merge AssertionList into AssertionSet
+        static inline void mergeAssertionSet( AssertionSet & dst, const AssertionList & src ) {
+                for ( const auto & s : src ) { dst.emplace( s ); }
+        }
 }
 
@@ -43 +48 @@
         ast::AssertionList need;   ///< Assertions which need to be resolved
 
-        Candidate() = default;
+        Candidate() : expr(), cost( Cost::zero ), cvtCost( Cost::zero ), env(), open(), need() {}
+        
+        Candidate( const ast::Expr * x, const ast::TypeEnvironment & e )
+        : expr( x ), cost( Cost::zero ), cvtCost( Cost::zero ), env( e ), open(), need() {}
+
+        Candidate( const Candidate & o, const ast::Expr * x )
+        : expr( x ), cost( o.cost ), cvtCost( Cost::zero ), env( o.env ), open( o.open ), 
+          need( o.need ) {}
+        
+        Candidate( 
+                const ast::Expr * x, ast::TypeEnvironment && e, ast::OpenVarSet && o, 
+                ast::AssertionSet && n, const Cost & c )
+        : expr( x ), cost( c ), cvtCost( Cost::zero ), env( std::move( e ) ), open( std::move( o ) ), 
+          need( n.begin(), n.end() ) {}
 };
 
@@ -51 +69 @@
 /// List of candidates
 using CandidateList = std::vector< CandidateRef >;
+
+/// Sum the cost of a list of candidates
+static inline Cost sumCost( const CandidateList & candidates ) {
+        Cost total = Cost::zero;
+        for ( const CandidateRef & r : candidates ) { total += r->cost; }
+        return total;
+}
 
 /// Holdover behaviour from old `findMinCost` -- xxx -- can maybe be eliminated?

src/ResolvExpr/CandidateFinder.cpp

@@ -16 +16 @@
 #include "CandidateFinder.hpp"
 
+#include <iterator>               // for back_inserter
 #include <sstream>
 #include <string>
@@ -26 +27 @@
 #include "SatisfyAssertions.hpp"
 #include "typeops.h"              // for adjustExprType
+#include "Unify.h"
 #include "AST/Expr.hpp"
 #include "AST/Node.hpp"
 #include "AST/Pass.hpp"
 #include "AST/Print.hpp"
+#include "AST/SymbolTable.hpp"
 #include "SymTab/Mangler.h"
 
@@ -39 +42 @@
 
         /// Actually visits expressions to find their candidate interpretations
-        struct Finder {
-                CandidateFinder & candFinder;
+        struct Finder final : public ast::WithShortCircuiting {
+                CandidateFinder & selfFinder;
                 const ast::SymbolTable & symtab;
                 CandidateList & candidates;
@@ -47 +50 @@
 
                 Finder( CandidateFinder & f )
-                : candFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ), 
+                : selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ), 
                   targetType( f.targetType ) {}
                 
-                #warning unimplemented
+                void previsit( const ast::Node * ) { visit_children = false; }
+
+                /// Convenience to add candidate to list
+                template<typename... Args>
+                void addCandidate( Args &&... args ) {
+                        candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
+                }
+
+                void postvisit( const ast::ApplicationExpr * applicationExpr ) {
+                        addCandidate( applicationExpr, tenv );
+                }
+
+                void postvisit( const ast::UntypedExpr * untypedExpr ) {
+                        #warning unimplemented
+                        (void)untypedExpr;
+                        assert(false);
+                }
+
+                /// true if expression is an lvalue
+                static bool isLvalue( const ast::Expr * x ) {
+                        return x->result && ( x->result->is_lvalue() || x->result.as< ast::ReferenceType >() );
+                }
+
+                void postvisit( const ast::AddressExpr * addressExpr ) {
+                        CandidateFinder finder{ symtab, tenv };
+                        finder.find( addressExpr->arg );
+                        for ( CandidateRef & r : finder.candidates ) {
+                                if ( ! isLvalue( r->expr ) ) continue;
+                                addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
+                        }
+                }
+
+                void postvisit( const ast::LabelAddressExpr * labelExpr ) {
+                        addCandidate( labelExpr, tenv );
+                }
+
+                void postvisit( const ast::CastExpr * castExpr ) {
+                        #warning unimplemented
+                        (void)castExpr;
+                        assert(false);
+                }
+
+                void postvisit( const ast::VirtualCastExpr * castExpr ) {
+                        assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
+                        CandidateFinder finder{ symtab, tenv };
+                        // don't prune here, all alternatives guaranteed to have same type
+                        finder.find( castExpr->arg, ResolvMode::withoutPrune() );
+                        for ( CandidateRef & r : finder.candidates ) {
+                                addCandidate( 
+                                        *r, new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
+                        }
+                }
+
+                void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
+                        #warning unimplemented
+                        (void)memberExpr;
+                        assert(false);
+                }
+
+                void postvisit( const ast::MemberExpr * memberExpr ) {
+                        addCandidate( memberExpr, tenv );
+                }
+
+                void postvisit( const ast::NameExpr * variableExpr ) {
+                        #warning unimplemented
+                        (void)variableExpr;
+                        assert(false);
+                }
+
+                void postvisit( const ast::VariableExpr * variableExpr ) {
+                        // not sufficient to just pass `variableExpr` here, type might have changed since
+                        // creation
+                        addCandidate( 
+                                new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
+                }
+
+                void postvisit( const ast::ConstantExpr * constantExpr ) {
+                        addCandidate( constantExpr, tenv );
+                }
+
+                void postvisit( const ast::SizeofExpr * sizeofExpr ) {
+                        #warning unimplemented
+                        (void)sizeofExpr;
+                        assert(false);
+                }
+
+                void postvisit( const ast::AlignofExpr * alignofExpr ) {
+                        #warning unimplemented
+                        (void)alignofExpr;
+                        assert(false);
+                }
+
+                void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
+                        #warning unimplemented
+                        (void)offsetofExpr;
+                        assert(false);
+                }
+
+                void postvisit( const ast::OffsetofExpr * offsetofExpr ) {
+                        addCandidate( offsetofExpr, tenv );
+                }
+
+                void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
+                        addCandidate( offsetPackExpr, tenv );
+                }
+
+                void postvisit( const ast::LogicalExpr * logicalExpr ) {
+                        CandidateFinder finder1{ symtab, tenv };
+                        finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
+                        if ( finder1.candidates.empty() ) return;
+
+                        CandidateFinder finder2{ symtab, tenv };
+                        finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
+                        if ( finder2.candidates.empty() ) return;
+
+                        for ( const CandidateRef & r1 : finder1.candidates ) {
+                                for ( const CandidateRef & r2 : finder2.candidates ) {
+                                        ast::TypeEnvironment env{ r1->env };
+                                        env.simpleCombine( r2->env );
+                                        ast::OpenVarSet open{ r1->open };
+                                        mergeOpenVars( open, r2->open );
+                                        ast::AssertionSet need;
+                                        mergeAssertionSet( need, r1->need );
+                                        mergeAssertionSet( need, r2->need );
+
+                                        addCandidate(
+                                                new ast::LogicalExpr{ 
+                                                        logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
+                                                std::move( env ), std::move( open ), std::move( need ), 
+                                                r1->cost + r2->cost );
+                                }
+                        }
+                }
+
+                void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
+                        // candidates for condition
+                        CandidateFinder finder1{ symtab, tenv };
+                        finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
+                        if ( finder1.candidates.empty() ) return;
+
+                        // candidates for true result
+                        CandidateFinder finder2{ symtab, tenv };
+                        finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
+                        if ( finder2.candidates.empty() ) return;
+
+                        // candidates for false result
+                        CandidateFinder finder3{ symtab, tenv };
+                        finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
+                        if ( finder3.candidates.empty() ) return;
+
+                        for ( const CandidateRef & r1 : finder1.candidates ) {
+                                for ( const CandidateRef & r2 : finder2.candidates ) {
+                                        for ( const CandidateRef & r3 : finder3.candidates ) {
+                                                ast::TypeEnvironment env{ r1->env };
+                                                env.simpleCombine( r2->env );
+                                                env.simpleCombine( r3->env );
+                                                ast::OpenVarSet open{ r1->open };
+                                                mergeOpenVars( open, r2->open );
+                                                mergeOpenVars( open, r3->open );
+                                                ast::AssertionSet need;
+                                                mergeAssertionSet( need, r1->need );
+                                                mergeAssertionSet( need, r2->need );
+                                                mergeAssertionSet( need, r3->need );
+                                                ast::AssertionSet have;
+
+                                                // unify true and false results, then infer parameters to produce new 
+                                                // candidates
+                                                ast::ptr< ast::Type > common;
+                                                if ( 
+                                                        unify( 
+                                                                r2->expr->result, r3->expr->result, env, need, have, open, symtab, 
+                                                                common ) 
+                                                ) {
+                                                        #warning unimplemented
+                                                        assert(false);
+                                                }
+                                        }
+                                }
+                        }
+                }
+
+                void postvisit( const ast::CommaExpr * commaExpr ) {
+                        ast::TypeEnvironment env{ tenv };
+                        ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env );
+                        
+                        CandidateFinder finder2{ symtab, env };
+                        finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
+
+                        for ( const CandidateRef & r2 : finder2.candidates ) {
+                                addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
+                        }
+                }
+
+                void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
+                        addCandidate( ctorExpr, tenv );
+                }
+
+                void postvisit( const ast::ConstructorExpr * ctorExpr ) {
+                        CandidateFinder finder{ symtab, tenv };
+                        finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
+                        for ( CandidateRef & r : finder.candidates ) {
+                                addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
+                        }
+                }
+
+                void postvisit( const ast::RangeExpr * rangeExpr ) {
+                        // resolve low and high, accept candidates where low and high types unify
+                        CandidateFinder finder1{ symtab, tenv };
+                        finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
+                        if ( finder1.candidates.empty() ) return;
+
+                        CandidateFinder finder2{ symtab, tenv };
+                        finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
+                        if ( finder2.candidates.empty() ) return;
+
+                        for ( const CandidateRef & r1 : finder1.candidates ) {
+                                for ( const CandidateRef & r2 : finder2.candidates ) {
+                                        ast::TypeEnvironment env{ r1->env };
+                                        env.simpleCombine( r2->env );
+                                        ast::OpenVarSet open{ r1->open };
+                                        mergeOpenVars( open, r2->open );
+                                        ast::AssertionSet need;
+                                        mergeAssertionSet( need, r1->need );
+                                        mergeAssertionSet( need, r2->need );
+                                        ast::AssertionSet have;
+
+                                        ast::ptr< ast::Type > common;
+                                        if ( 
+                                                unify( 
+                                                        r1->expr->result, r2->expr->result, env, need, have, open, symtab, 
+                                                        common ) 
+                                        ) {
+                                                ast::RangeExpr * newExpr = 
+                                                        new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
+                                                newExpr->result = common ? common : r1->expr->result;
+                                                
+                                                #warning unimplemented
+                                                assert(false);
+                                        }
+                                }
+                        }
+                }
+
+                void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
+                        std::vector< CandidateFinder > subCandidates = 
+                                selfFinder.findSubExprs( tupleExpr->exprs );
+                        std::vector< CandidateList > possibilities;
+                        combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
+
+                        for ( const CandidateList & subs : possibilities ) {
+                                std::vector< ast::ptr< ast::Expr > > exprs;
+                                exprs.reserve( subs.size() );
+                                for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
+
+                                ast::TypeEnvironment env;
+                                ast::OpenVarSet open;
+                                ast::AssertionSet need;
+                                for ( const CandidateRef & sub : subs ) {
+                                        env.simpleCombine( sub->env );
+                                        mergeOpenVars( open, sub->open );
+                                        mergeAssertionSet( need, sub->need );
+                                }
+
+                                addCandidate(
+                                        new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) }, 
+                                        std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
+                        }
+                }
+
+                void postvisit( const ast::TupleExpr * tupleExpr ) {
+                        addCandidate( tupleExpr, tenv );
+                }
+
+                void postvisit( const ast::TupleIndexExpr * tupleExpr ) {
+                        addCandidate( tupleExpr, tenv );
+                }
+
+                void postvisit( const ast::TupleAssignExpr * tupleExpr ) {
+                        addCandidate( tupleExpr, tenv );
+                }
+
+                void postvisit( const ast::UniqueExpr * unqExpr ) {
+                        CandidateFinder finder{ symtab, tenv };
+                        finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
+                        for ( CandidateRef & r : finder.candidates ) {
+                                // ensure that the the id is passed on so that the expressions are "linked"
+                                addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
+                        }
+                }
+
+                void postvisit( const ast::StmtExpr * stmtExpr ) {
+                        #warning unimplemented
+                        (void)stmtExpr;
+                        assert(false);
+                }
+
+                void postvisit( const ast::UntypedInitExpr * initExpr ) {
+                        #warning unimplemented
+                        (void)initExpr;
+                        assert(false);
+                }
+
+                void postvisit( const ast::InitExpr * ) {
+                        assertf( false, "CandidateFinder should never see a resolved InitExpr." );
+                }
+
+                void postvisit( const ast::DeletedExpr * ) {
+                        assertf( false, "CandidateFinder should never see a DeletedExpr." );
+                }
+
+                void postvisit( const ast::GenericExpr * ) {
+                        assertf( false, "_Generic is not yet supported." );
+                }
         };
 

src/ResolvExpr/Resolver.cc

@@ -1100 +1100 @@
                         StripCasts_new::strip( expr );
                 }
-
-                /// Find the expression candidate that is the unique best match for `untyped` in a `void`
-                /// context.
-                ast::ptr< ast::Expr > resolveInVoidContext(
-                        const ast::Expr * expr, const ast::SymbolTable & symtab, ast::TypeEnvironment & env
-                ) {
-                        assertf( expr, "expected a non-null expression" );
-                        
-                        // set up and resolve expression cast to void
-                        ast::CastExpr * untyped = new ast::CastExpr{ expr->location, expr };
-                        CandidateRef choice = findUnfinishedKindExpression( 
-                                untyped, symtab, "", anyCandidate, ResolvMode::withAdjustment() );
-                        
-                        // a cast expression has either 0 or 1 interpretations (by language rules);
-                        // if 0, an exception has already been thrown, and this code will not run
-                        const ast::CastExpr * castExpr = choice->expr.strict_as< ast::CastExpr >();
-                        env = std::move( choice->env );
-
-                        return castExpr->arg;
-                }
-
+        } // anonymous namespace
+
+                
+        ast::ptr< ast::Expr > resolveInVoidContext(
+                const ast::Expr * expr, const ast::SymbolTable & symtab, ast::TypeEnvironment & env
+        ) {
+                assertf( expr, "expected a non-null expression" );
+                
+                // set up and resolve expression cast to void
+                ast::CastExpr * untyped = new ast::CastExpr{ expr->location, expr };
+                CandidateRef choice = findUnfinishedKindExpression( 
+                        untyped, symtab, "", anyCandidate, ResolvMode::withAdjustment() );
+                
+                // a cast expression has either 0 or 1 interpretations (by language rules);
+                // if 0, an exception has already been thrown, and this code will not run
+                const ast::CastExpr * castExpr = choice->expr.strict_as< ast::CastExpr >();
+                env = std::move( choice->env );
+
+                return castExpr->arg;
+        }
+
+        namespace {
                 /// Resolve `untyped` to the expression whose candidate is the best match for a `void` 
                 /// context.

src/ResolvExpr/Resolver.h

@@ -17 +17 @@
 
 #include <list>          // for list
-#include <AST/Node.hpp>  // for ptr
+
+#include "AST/Node.hpp"  // for ptr
 
 class ConstructorInit;
@@ -30 +31 @@
         class Decl;
         class DeletedExpr;
+        class SymbolTable;
+        class TypeEnvironment;
 } // namespace ast
 
@@ -51 +54 @@
         /// Searches expr and returns the first DeletedExpr found, otherwise nullptr
         const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr );
+        /// Find the expression candidate that is the unique best match for `untyped` in a `void`
+        /// context.
+        ast::ptr< ast::Expr > resolveInVoidContext(
+                const ast::Expr * expr, const ast::SymbolTable & symtab, ast::TypeEnvironment & env );
 } // namespace ResolvExpr