Changeset 234b1cb for src/Tuples/TupleAssignment.cc

Timestamp:

Jun 20, 2019, 2:32:55 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:

b8524ca, f5edcb4

Parents:

c0f9efe

Message:

Port TupleAssignment? to new AST

File:

• src/Tuples/TupleAssignment.cc (modified) (13 diffs)

src/Tuples/TupleAssignment.cc

@@ -22 +22 @@
 #include <vector>
 
+#include "AST/Decl.hpp"
+#include "AST/Init.hpp"
+#include "AST/Pass.hpp"
+#include "AST/Stmt.hpp"
+#include "AST/TypeEnvironment.hpp"
 #include "CodeGen/OperatorTable.h"
 #include "Common/PassVisitor.h"
 #include "Common/UniqueName.h"             // for UniqueName
-#include "Common/utility.h"                // for zipWith
+#include "Common/utility.h"                // for splice, zipWith
 #include "Explode.h"                       // for explode
 #include "InitTweak/GenInit.h"             // for genCtorInit
@@ -51 +56 @@
 
 namespace Tuples {
-        class TupleAssignSpotter {
+        class TupleAssignSpotter_old {
           public:
                 // dispatcher for Tuple (multiple and mass) assignment operations
-                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
+                TupleAssignSpotter_old( ResolvExpr::AlternativeFinder & );
                 void spot( UntypedExpr * expr, std::vector<ResolvExpr::AlternativeFinder> &args );
 
@@ -62 +67 @@
                 struct Matcher {
                   public:
-                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, 
+                        Matcher( TupleAssignSpotter_old &spotter, const ResolvExpr::AltList& lhs, 
                                 const ResolvExpr::AltList& rhs );
                         virtual ~Matcher() {}
@@ -80 +85 @@
                         
                         ResolvExpr::AltList lhs, rhs;
-                        TupleAssignSpotter &spotter;
+                        TupleAssignSpotter_old &spotter;
                         ResolvExpr::Cost baseCost;
                         std::list< ObjectDecl * > tmpDecls;
@@ -90 +95 @@
                 struct MassAssignMatcher : public Matcher {
                   public:
-                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
+                        MassAssignMatcher( TupleAssignSpotter_old &spotter, const ResolvExpr::AltList& lhs,
                                 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
                         virtual void match( std::list< Expression * > &out );
@@ -97 +102 @@
                 struct MultipleAssignMatcher : public Matcher {
                   public:
-                        MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
+                        MultipleAssignMatcher( TupleAssignSpotter_old &spotter, const ResolvExpr::AltList& lhs,
                                 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
                         virtual void match( std::list< Expression * > &out );
@@ -136 +141 @@
         void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr,
                                 std::vector<ResolvExpr::AlternativeFinder> &args ) {
-                TupleAssignSpotter spotter( currentFinder );
+                TupleAssignSpotter_old spotter( currentFinder );
                 spotter.spot( expr, args );
         }
 
-        TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
+        TupleAssignSpotter_old::TupleAssignSpotter_old( ResolvExpr::AlternativeFinder &f )
                 : currentFinder(f) {}
 
-        void TupleAssignSpotter::spot( UntypedExpr * expr,
+        void TupleAssignSpotter_old::spot( UntypedExpr * expr,
                         std::vector<ResolvExpr::AlternativeFinder> &args ) {
                 if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
@@ -224 +229 @@
         }
 
-        void TupleAssignSpotter::match() {
+        void TupleAssignSpotter_old::match() {
                 assert ( matcher != 0 );
 
@@ -275 +280 @@
         }
 
-        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter,
+        TupleAssignSpotter_old::Matcher::Matcher( TupleAssignSpotter_old &spotter,
                 const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs )
         : lhs(lhs), rhs(rhs), spotter(spotter),
@@ -313 +318 @@
         };
 
-        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
+        ObjectDecl * TupleAssignSpotter_old::Matcher::newObject( UniqueName & namer, Expression * expr ) {
                 assert( expr->result && ! expr->get_result()->isVoid() );
                 ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->result->clone(), new SingleInit( expr->clone() ) );
@@ -329 +334 @@
         }
 
-        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
+        void TupleAssignSpotter_old::MassAssignMatcher::match( std::list< Expression * > &out ) {
                 static UniqueName lhsNamer( "__massassign_L" );
                 static UniqueName rhsNamer( "__massassign_R" );
@@ -347 +352 @@
         }
 
-        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
+        void TupleAssignSpotter_old::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
                 static UniqueName lhsNamer( "__multassign_L" );
                 static UniqueName rhsNamer( "__multassign_R" );
@@ -378 +383 @@
         }
 
-        void handleTupleAssignment( 
-                ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign, 
-                std::vector< ResolvExpr::CandidateFinder > & args
-        ) {
-                #warning unimplmented
-                (void)finder; (void)assign; (void)args;
-                assert(false);
-        }
+namespace {
+        /// true if `expr` is of tuple type
+        bool isTuple( const ast::Expr * expr ) {
+                if ( ! expr ) return false;
+                assert( expr->result );
+                return dynamic_cast< const ast::TupleType * >( expr->result->stripReferences() );
+        }
+        
+        /// true if `expr` is of tuple type or a reference to one
+        bool refToTuple( const ast::Expr * expr ) {
+                assert( expr->result );
+                // check for function returning tuple of reference types
+                if ( auto castExpr = dynamic_cast< const ast::CastExpr * >( expr ) ) {
+                        return refToTuple( castExpr->arg );
+                } else {
+                        return isTuple( expr );
+                }
+        }
+
+        /// Dispatcher for tuple (multiple and mass) assignment operations
+        class TupleAssignSpotter_new final {
+                /// Actually finds tuple assignment operations, by subclass
+                struct Matcher {
+                        ResolvExpr::CandidateList lhs, rhs;
+                        TupleAssignSpotter_new & spotter;
+                        CodeLocation location;
+                        ResolvExpr::Cost baseCost;
+                        std::vector< ast::ptr< ast::ObjectDecl > > tmpDecls;
+                        ast::TypeEnvironment env;
+                        ast::OpenVarSet open;
+                        ast::AssertionSet need;
+
+                        void combineState( const ResolvExpr::Candidate & cand ) {
+                                env.simpleCombine( cand.env );
+                                ast::mergeOpenVars( open, cand.open );
+                                need.insert( cand.need.begin(), cand.need.end() );
+                        }
+
+                        Matcher( 
+                                TupleAssignSpotter_new & s, const CodeLocation & loc,
+                                const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
+                        : lhs( l ), rhs( r ), spotter( s ), location( loc ), 
+                          baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ), tmpDecls(), 
+                          env(), open(), need() {
+                                for ( auto & cand : lhs ) combineState( *cand );
+                                for ( auto & cand : rhs ) combineState( *cand );
+                        }
+
+                        virtual std::vector< ast::ptr< ast::Expr > > match() = 0;
+
+                        /// removes environments from subexpressions within statement expressions, which could 
+                        /// throw off later passes like those in Box which rely on PolyMutator, and adds the 
+                        /// bindings to the env
+                        struct EnvRemover {
+                                /// environment to hoist ExprStmt environments to
+                                ast::TypeEnvironment & tenv;
+
+                                EnvRemover( ast::TypeEnvironment & e ) : tenv( e ) {}
+
+                                const ast::ExprStmt * previsit( const ast::ExprStmt * stmt ) {
+                                        if ( stmt->expr->env ) {
+                                                tenv.add( *stmt->expr->env );
+                                                ast::ExprStmt * mut = mutate( stmt );
+                                                mut->expr.get_and_mutate()->env = nullptr;
+                                                return mut;
+                                        }
+                                        return stmt;
+                                }
+                        };
+
+                        ast::ObjectDecl * newObject( UniqueName & namer, const ast::Expr * expr ) {
+                                assert( expr->result && ! expr->result->isVoid() );
+                                
+                                ast::ObjectDecl * ret = new ast::ObjectDecl{ 
+                                        location, namer.newName(), expr->result, new ast::SingleInit{ location, expr }, 
+                                        ast::Storage::Classes{}, ast::Linkage::Cforall };
+                                
+                                // if expression type is a reference, just need an initializer, otherwise construct
+                                if ( ! expr->result.as< ast::ReferenceType >() ) {
+                                        // resolve ctor/dtor for the new object
+                                        ast::ptr< ast::Init > ctorInit = ResolvExpr::resolveCtorInit( 
+                                                        InitTweak::genCtorInit( ret ), spotter.crntFinder.symtab );
+                                        // remove environments from subexpressions of stmtExpr
+                                        ast::Pass< EnvRemover > rm{ env };
+                                        ret->init = ctorInit->accept( rm );
+                                }
+
+                                PRINT( std::cerr << "new object: " << ret << std::endl; )
+                                return ret;
+                        }
+
+                        ast::UntypedExpr * createFunc( 
+                                const std::string & fname, const ast::ObjectDecl * left, 
+                                const ast::ObjectDecl * right 
+                        ) {
+                                assert( left );
+                                std::vector< ast::ptr< ast::Expr > > args;
+                                args.emplace_back( new ast::VariableExpr{ location, left } );
+                                if ( right ) { args.emplace_back( new ast::VariableExpr{ location, right } ); }
+
+                                if ( left->type->referenceDepth() > 1 && CodeGen::isConstructor( fname ) ) {
+                                        args.front() = new ast::AddressExpr{ location, args.front() };
+                                        if ( right ) { args.back() = new ast::AddressExpr{ location, args.back() }; }
+                                        return new ast::UntypedExpr{ 
+                                                location, new ast::NameExpr{ location, "?=?" }, std::move(args) };
+                                } else {
+                                        return new ast::UntypedExpr{ 
+                                                location, new ast::NameExpr{ location, fname }, std::move(args) };
+                                }
+                        }
+                };
+
+                /// Finds mass-assignment operations
+                struct MassAssignMatcher final : public Matcher {
+                        MassAssignMatcher(
+                                TupleAssignSpotter_new & s, const CodeLocation & loc, 
+                                const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
+                        : Matcher( s, loc, l, r ) {}
+
+                        std::vector< ast::ptr< ast::Expr > > match() override {
+                                static UniqueName lhsNamer( "__massassign_L" );
+                                static UniqueName rhsNamer( "__massassign_R" );
+                                // empty tuple case falls into this matcher
+                                assert( lhs.empty() ? rhs.empty() : rhs.size() <= 1 );
+
+                                ast::ptr< ast::ObjectDecl > rtmp = 
+                                        rhs.size() == 1 ? newObject( rhsNamer, rhs.front()->expr ) : nullptr;
+
+                                std::vector< ast::ptr< ast::Expr > > out;
+                                for ( ResolvExpr::CandidateRef & lhsCand : lhs ) {
+                                        // create a temporary object for each value in the LHS and create a call 
+                                        // involving the RHS
+                                        ast::ptr< ast::ObjectDecl > ltmp = newObject( lhsNamer, lhsCand->expr );
+                                        out.emplace_back( createFunc( spotter.fname, ltmp, rtmp ) );
+                                        tmpDecls.emplace_back( std::move( ltmp ) );
+                                }
+                                if ( rtmp ) tmpDecls.emplace_back( std::move( rtmp ) );
+
+                                return out;
+                        }
+                };
+
+                /// Finds multiple-assignment operations
+                struct MultipleAssignMatcher final : public Matcher {
+                        MultipleAssignMatcher(
+                                TupleAssignSpotter_new & s, const CodeLocation & loc, 
+                                const ResolvExpr::CandidateList & l, const ResolvExpr::CandidateList & r )
+                        : Matcher( s, loc, l, r ) {}
+
+                        std::vector< ast::ptr< ast::Expr > > match() override {
+                                static UniqueName lhsNamer( "__multassign_L" );
+                                static UniqueName rhsNamer( "__multassign_R" );
+
+                                if ( lhs.size() != rhs.size() ) return {};
+
+                                // produce a new temporary object for each value in the LHS and RHS and pairwise 
+                                // create the calls
+                                std::vector< ast::ptr< ast::ObjectDecl > > ltmp, rtmp;
+
+                                std::vector< ast::ptr< ast::Expr > > out;
+                                for ( unsigned i = 0; i < lhs.size(); ++i ) {
+                                        ResolvExpr::CandidateRef & lhsCand = lhs[i];
+                                        ResolvExpr::CandidateRef & rhsCand = rhs[i];
+
+                                        // convert RHS to LHS type minus one reference -- important for case where LHS 
+                                        // is && and RHS is lvalue
+                                        auto lhsType = lhsCand->expr->result.strict_as< ast::ReferenceType >();
+                                        rhsCand->expr = new ast::CastExpr{ 
+                                                rhsCand->expr->location, rhsCand->expr, lhsType->base };
+                                        ast::ptr< ast::ObjectDecl > lobj = newObject( lhsNamer, lhsCand->expr );
+                                        ast::ptr< ast::ObjectDecl > robj = newObject( rhsNamer, rhsCand->expr );
+                                        out.emplace_back( createFunc( spotter.fname, lobj, robj ) );
+                                        ltmp.emplace_back( std::move( lobj ) );
+                                        rtmp.emplace_back( std::move( robj ) );
+
+                                        // resolve the cast expression so that rhsCand return type is bound by the cast 
+                                        // type as needed, and transfer the resulting environment
+                                        ResolvExpr::CandidateFinder finder{ spotter.crntFinder.symtab, env };
+                                        finder.find( rhsCand->expr, ResolvExpr::ResolvMode::withAdjustment() );
+                                        assert( finder.candidates.size() == 1 );
+                                        env = std::move( finder.candidates.front()->env );
+                                }
+                                
+                                splice( tmpDecls, ltmp );
+                                splice( tmpDecls, rtmp );
+                                
+                                return out;
+                        }
+                };
+
+                ResolvExpr::CandidateFinder & crntFinder;
+                std::string fname;
+                std::unique_ptr< Matcher > matcher;
+        
+        public:
+                TupleAssignSpotter_new( ResolvExpr::CandidateFinder & f ) 
+                : crntFinder( f ), fname(), matcher() {}
+
+                // find left- and right-hand-sides for mass or multiple assignment
+                void spot( 
+                        const ast::UntypedExpr * expr, std::vector< ResolvExpr::CandidateFinder > & args 
+                ) {
+                        if ( auto op = expr->func.as< ast::NameExpr >() ) {
+                                // skip non-assignment functions
+                                if ( ! CodeGen::isCtorDtorAssign( op->name ) ) return;
+                                fname = op->name;
+
+                                // handled by CandidateFinder if applicable (both odd cases)
+                                if ( args.empty() || ( args.size() == 1 && CodeGen::isAssignment( fname ) ) ) {
+                                        return;
+                                }
+
+                                // look over all possible left-hand-side
+                                for ( ResolvExpr::CandidateRef & lhsCand : args[0] ) {
+                                        // skip non-tuple LHS
+                                        if ( ! refToTuple( lhsCand->expr ) ) continue;
+
+                                        // explode is aware of casts - ensure every LHS is sent into explode with a 
+                                        // reference cast
+                                        if ( ! lhsCand->expr.as< ast::CastExpr >() ) {
+                                                lhsCand->expr = new ast::CastExpr{ 
+                                                        lhsCand->expr->location, lhsCand->expr, 
+                                                        new ast::ReferenceType{ lhsCand->expr->result } };
+                                        }
+
+                                        // explode the LHS so that each field of a tuple-valued expr is assigned
+                                        ResolvExpr::CandidateList lhs;
+                                        explode( *lhsCand, crntFinder.symtab, back_inserter(lhs), true );
+                                        for ( ResolvExpr::CandidateRef & cand : lhs ) {
+                                                // each LHS value must be a reference - some come in with a cast, if not 
+                                                // just cast to reference here
+                                                if ( ! cand->expr->result.as< ast::ReferenceType >() ) {
+                                                        cand->expr = new ast::CastExpr{
+                                                                cand->expr->location, cand->expr, 
+                                                                new ast::ReferenceType{ cand->expr->result } };
+                                                }
+                                        }
+
+                                        if ( args.size() == 1 ) {
+                                                // mass default-initialization/destruction
+                                                ResolvExpr::CandidateList rhs{};
+                                                matcher.reset( new MassAssignMatcher{ *this, expr->location, lhs, rhs } );
+                                                match();
+                                        } else if ( args.size() == 2 ) {
+                                                for ( const ResolvExpr::CandidateRef & rhsCand : args[1] ) {
+                                                        ResolvExpr::CandidateList rhs;
+                                                        if ( isTuple( rhsCand->expr ) ) {
+                                                                // multiple assignment
+                                                                explode( *rhsCand, crntFinder.symtab, back_inserter(rhs), true );
+                                                                matcher.reset( 
+                                                                        new MultipleAssignMatcher{ *this, expr->location, lhs, rhs } );
+                                                        } else {
+                                                                // mass assignment
+                                                                rhs.emplace_back( rhsCand );
+                                                                matcher.reset( 
+                                                                        new MassAssignMatcher{ *this, expr->location, lhs, rhs } );
+                                                        }
+                                                        match();
+                                                }
+                                        } else {
+                                                // expand all possible RHS possibilities
+                                                std::vector< ResolvExpr::CandidateList > rhsCands;
+                                                combos( 
+                                                        std::next( args.begin(), 1 ), args.end(), back_inserter( rhsCands ) );
+                                                for ( const ResolvExpr::CandidateList & rhsCand : rhsCands ) {
+                                                        // multiple assignment
+                                                        ResolvExpr::CandidateList rhs;
+                                                        explode( rhsCand, crntFinder.symtab, back_inserter(rhs), true );
+                                                        matcher.reset( 
+                                                                new MultipleAssignMatcher{ *this, expr->location, lhs, rhs } );
+                                                        match();
+                                                }
+                                        }
+                                }
+                        }
+                }
+
+                void match() {
+                        assert( matcher );
+
+                        std::vector< ast::ptr< ast::Expr > > newAssigns = matcher->match();
+
+                        if ( ! ( matcher->lhs.empty() && matcher->rhs.empty() ) ) {
+                                // if both LHS and RHS are empty than this is the empty tuple case, wherein it's 
+                                // okay for newAssigns to be empty. Otherwise, return early so that no new 
+                                // candidates are generated
+                                if ( newAssigns.empty() ) return;
+                        }
+
+                        ResolvExpr::CandidateList crnt;
+                        // now resolve new assignments
+                        for ( const ast::Expr * expr : newAssigns ) {
+                                PRINT(
+                                        std::cerr << "== resolving tuple assign ==" << std::endl;
+                                        std::cerr << expr << std::endl;
+                                )
+
+                                ResolvExpr::CandidateFinder finder{ crntFinder.symtab, matcher->env };
+
+                                try {
+                                        finder.find( expr, ResolvExpr::ResolvMode::withAdjustment() );
+                                } catch (...) {
+                                        // no match is not failure, just that this tuple assignment is invalid
+                                        return;
+                                }
+
+                                ResolvExpr::CandidateList & cands = finder.candidates;
+                                assert( cands.size() == 1 );
+                                assert( cands.front()->expr );
+                                crnt.emplace_back( std::move( cands.front() ) );
+                        }
+
+                        // extract expressions from the assignment candidates to produce a list of assignments 
+                        // that together form a sigle candidate
+                        std::vector< ast::ptr< ast::Expr > > solved;
+                        for ( ResolvExpr::CandidateRef & cand : crnt ) {
+                                solved.emplace_back( cand->expr );
+                                matcher->combineState( *cand );
+                        }
+
+                        crntFinder.candidates.emplace_back( std::make_shared< ResolvExpr::Candidate >(
+                                new ast::TupleAssignExpr{ 
+                                        matcher->location, std::move( solved ), std::move( matcher->tmpDecls ) }, 
+                                std::move( matcher->env ), std::move( matcher->open ), std::move( matcher->need ), 
+                                ResolvExpr::sumCost( crnt ) + matcher->baseCost ) );
+                }
+        };
+} // anonymous namespace
+
+void handleTupleAssignment( 
+        ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign, 
+        std::vector< ResolvExpr::CandidateFinder > & args
+) {
+        TupleAssignSpotter_new spotter{ finder };
+        spotter.spot( assign, args );
+}
+
 } // namespace Tuples