Changeset b067d9b for src/Tuples

Timestamp:

Oct 29, 2019, 4:01:24 PM (6 years ago)

Author:

Thierry Delisle <tdelisle@…>

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, stuck-waitfor-destruct

Children:

773db65, 9421f3d8

Parents:

7951100 (diff), 8364209 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:

src/Tuples

Files:

• Explode.cc (modified) (2 diffs)
• Explode.h (modified) (6 diffs)
• TupleAssignment.cc (modified) (11 diffs)
• TupleExpansion.cc (modified) (10 diffs)
• Tuples.cc (added)
• Tuples.h (modified) (4 diffs)
• module.mk (modified) (1 diff)

src/Tuples/Explode.cc

@@ -9 +9 @@
 // Author           : Rob Schluntz
 // Created On       : Wed Nov 9 13:12:24 2016
-// Last Modified By : Rob Schluntz
-// Last Modified On : Wed Nov 9 13:20:24 2016
-// Update Count     : 2
+// Last Modified By : Andrew Beach
+// Last Modified On : Wed Jun 12 16:40:00 2016
+// Update Count     : 3
 //
 
@@ -106 +106 @@
                 return expr;
         }
+
+namespace {
+
+// Remove one level of reference from a reference type.
+const ast::Type * getReferenceBase( const ast::Type * t ) {
+        if ( const ast::ReferenceType * ref = dynamic_cast< const ast::ReferenceType * >( t ) ) {
+                return ref->base;
+        } else {
+                assertf( false, "getReferenceBase for non-ref: %s", toString( t ).c_str() );
+                return nullptr;
+        }
+}
+
+struct CastExploderCore {
+        bool castAdded = false;
+        bool foundUniqueExpr = false;
+        const ast::Expr * applyCast( const ast::Expr * expr, bool first = true ) {
+                // On tuple push the cast down.
+                if ( const ast::TupleExpr * tupleExpr = dynamic_cast< const ast::TupleExpr * >( expr ) ) {
+                        foundUniqueExpr = true;
+                        std::vector< ast::ptr< ast::Expr > > exprs;
+                        for ( const ast::Expr * expr : tupleExpr->exprs ) {
+                                exprs.emplace_back( applyCast( expr, false ) );
+                                //exprs.emplace_back( ast::ptr< ast::Expr >( applyCast( expr, false ) ) );
+                        }
+                        if ( first ) {
+                                castAdded = true;
+                                const ast::Expr * tuple = new ast::TupleExpr{
+                                        tupleExpr->location, std::move( exprs ) };
+                                return new ast::CastExpr{ tuple, new ast::ReferenceType{ tuple->result } };
+                        } else {
+                                return new ast::TupleExpr( tupleExpr->location, std::move( exprs ) );
+                        }
+                }
+                if ( dynamic_cast< const ast::ReferenceType * >( expr->result.get() ) ) {
+                        return expr;
+                } else {
+                        castAdded = true;
+                        return new ast::CastExpr{ expr, new ast::ReferenceType{ expr->result } };
+                }
+        }
+
+        const ast::Expr * postmutate( const ast::UniqueExpr * node ) {
+                // move cast into unique expr so that the unique expr has type T& rather than
+                // type T. In particular, this transformation helps with generating the
+                // correct code for reference-cast member tuple expressions, since the result
+                // should now be a tuple of references rather than a reference to a tuple.
+                // Still, this code is a bit awkward, and could use some improvement.
+                const ast::UniqueExpr * newNode = new ast::UniqueExpr( node->location,
+                                applyCast( node->expr ), node->id );
+                if ( castAdded ) {
+                        // if a cast was added by applyCast, then unique expr now has one more layer of reference
+                        // than it had coming into this function. To ensure types still match correctly, need to cast
+                        //  to reference base so that outer expressions are still correct.
+                        castAdded = false;
+                        const ast::Type * newType = getReferenceBase( newNode->result );
+                        return new ast::CastExpr{ newNode->location, node, newType };
+                }
+                return newNode;
+        }
+
+        const ast::Expr * postmutate( const ast::TupleIndexExpr * tupleExpr ) {
+                // tuple index expr needs to be rebuilt to ensure that the type of the
+                // field is consistent with the type of the tuple expr, since the field
+                // may have changed from type T to T&.
+                return new ast::TupleIndexExpr( tupleExpr->location, tupleExpr->tuple, tupleExpr->index );
+        }
+};
+
+} // namespace
+
+const ast::Expr * distributeReference( const ast::Expr * expr ) {
+        ast::Pass<CastExploderCore> exploder;
+        expr = expr->accept( exploder );
+        if ( ! exploder.pass.foundUniqueExpr ) {
+                expr = new ast::CastExpr{ expr, new ast::ReferenceType{ expr->result } };
+        }
+        return expr;
+}
+
 } // namespace Tuples
 

src/Tuples/Explode.h

@@ -9 +9 @@
 // Author           : Rob Schluntz
 // Created On       : Wed Nov 9 13:12:24 2016
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 22 09:55:16 2017
-// Update Count     : 3
+// Last Modified By : Andrew Beach
+// Last Modified On : Mon Jun 17 14:36:00 2019
+// Update Count     : 4
 //
 
@@ -19 +19 @@
 #include <utility>                      // for forward
 
+#include "AST/Expr.hpp"
 #include "ResolvExpr/Alternative.h"     // for Alternative, AltList
+#include "ResolvExpr/Candidate.hpp"     // for Candidate, CandidateList
 #include "ResolvExpr/ExplodedActual.h"  // for ExplodedActual
+#include "ResolvExpr/ExplodedArg.hpp"   // for ExplodedArg
 #include "SynTree/Expression.h"         // for Expression, UniqueExpr, AddressExpr
 #include "SynTree/Type.h"               // for TupleType, Type
 #include "Tuples.h"                     // for maybeImpure
+
+namespace ast {
+        class SymbolTable;
+}
 
 namespace SymTab {
@@ -44 +51 @@
         template<typename OutputIterator>
         void append( OutputIterator out, Expression* expr, const ResolvExpr::TypeEnvironment& env,
+                        const ResolvExpr::OpenVarSet& openVars, const ResolvExpr::AssertionList& need,
                         const ResolvExpr::Cost& cost, const ResolvExpr::Cost& cvtCost ) {
-                *out++ = ResolvExpr::Alternative{ expr, env, cost, cvtCost };
+                *out++ = ResolvExpr::Alternative{ expr, env, openVars, need, cost, cvtCost };
         }
 
         /// Append alternative to an ExplodedActual
         static inline void append( ResolvExpr::ExplodedActual& ea, Expression* expr,
-                        const ResolvExpr::TypeEnvironment&, const ResolvExpr::Cost&, const ResolvExpr::Cost& ) {
+                        const ResolvExpr::TypeEnvironment&, const ResolvExpr::OpenVarSet&,
+                        const ResolvExpr::AssertionList&, const ResolvExpr::Cost&, const ResolvExpr::Cost& ) {
                 ea.exprs.emplace_back( expr );
-                /// xxx -- merge environment, cost?
+                /// xxx -- merge environment, openVars, need, cost?
         }
 
@@ -68 +77 @@
                                         // distribute reference cast over all components
                                         append( std::forward<Output>(out), distributeReference( alt.release_expr() ),
-                                                alt.env, alt.cost, alt.cvtCost );
+                                                alt.env, alt.openVars, alt.need, alt.cost, alt.cvtCost );
                                 }
                                 // in tuple assignment, still need to handle the other cases, but only if not already handled here (don't want to output too many alternatives)
@@ -102 +111 @@
                 } else {
                         // atomic (non-tuple) type - output a clone of the expression in a new alternative
-                        append( std::forward<Output>(out), expr->clone(), alt.env, alt.cost, alt.cvtCost );
+                        append( std::forward<Output>(out), expr->clone(), alt.env, alt.openVars, alt.need,
+                                alt.cost, alt.cvtCost );
                 }
         }
@@ -127 +137 @@
                 explode( alts.begin(), alts.end(), indexer, std::forward<Output>(out), isTupleAssign );
         }
+
+const ast::Expr * distributeReference( const ast::Expr * );
+
+/// Append candidate to an OutputIterator of Candidates.
+template<typename OutputIterator>
+void append( OutputIterator out, const ast::Expr * expr, const ast::TypeEnvironment & env,
+                const ast::OpenVarSet & open, const ast::AssertionList & need,
+                const ResolvExpr::Cost & cost, const ResolvExpr::Cost & cvtCost ) {
+        ast::TypeEnvironment copyEnv = env;
+        ast::OpenVarSet copyOpen = open;
+        ast::AssertionSet set;
+        mergeAssertionSet( set, need );
+        *out++ = std::make_shared<ResolvExpr::Candidate>( expr, std::move( copyEnv ),
+                std::move( copyOpen ), std::move( set ), cost, cvtCost );
+}
+
+/// Append candidate to an ExplodedArg.
+static inline void append( ResolvExpr::ExplodedArg& ea, const ast::Expr * expr,
+                const ast::TypeEnvironment&, const ast::OpenVarSet&,
+                const ast::AssertionList&, const ResolvExpr::Cost&, const ResolvExpr::Cost& ) {
+        // I'm not sure why most of the arguments are unused. But they were in the old version.
+        ea.exprs.emplace_back( expr );
+}
+
+/// Check if the expression is a cast to a reference type, return it if it is.
+static inline const ast::CastExpr * isReferenceCast( const ast::Expr * expr ) {
+        if ( const ast::CastExpr * cast = dynamic_cast< const ast::CastExpr * >( expr ) ) {
+                if ( dynamic_cast< const ast::ReferenceType * >( cast->result.get() ) ) {
+                        return cast;
+                }
+        }
+        return nullptr;
+}
+
+/// helper function (indirectely) used by explode
+template< typename Output >
+void explodeRecursive(
+        const ast::CastExpr *, const ResolvExpr::Candidate &,
+        const ast::SymbolTable &, Output &&
+) {
+}
+
+/// helper function used by explode
+template< typename Output >
+void explodeUnique(
+        const ast::ptr< ast::Expr > & expr, const ResolvExpr::Candidate & arg,
+        const ast::SymbolTable & symtab, Output && out, bool isTupleAssign
+) {
+        // Tuple assignment can use a faster method if it is cast. Uses recursive exploding.
+        if ( isTupleAssign ) if ( const ast::CastExpr * castExpr = isReferenceCast( expr ) ) {
+                ResolvExpr::CandidateList candidates;
+                explodeUnique( castExpr->arg, arg, symtab, back_inserter( candidates ), true );
+                for ( ResolvExpr::CandidateRef & cand : candidates ) {
+                        // Distribute the reference cast over all components of the candidate.
+                        append( std::forward<Output>(out), distributeReference( cand->expr ), cand->env,
+                                cand->open, cand->need, cand->cost, cand->cvtCost );
+                }
+                return;
+        }
+        const ast::Type * res = expr->result->stripReferences();
+        if ( const ast::TupleType * tupleType = dynamic_cast< const ast::TupleType * >( res ) ) {
+                if ( const ast::ptr< ast::TupleExpr > & tupleExpr = expr.as< ast::TupleExpr >() ) {
+                        // Open the tuple expr and continue on its components.
+                        for ( const ast::Expr * expr : tupleExpr->exprs ) {
+                                explodeUnique( expr, arg, symtab, std::forward<Output>(out), isTupleAssign );
+                        }
+                } else {
+                        ast::ptr< ast::Expr > local = expr;
+                        // Expressions which may have side effects require a single unique instance.
+                        if ( Tuples::maybeImpureIgnoreUnique( local ) ) {
+                                local = new ast::UniqueExpr( local->location, local );
+                        }
+                        // Cast a reference away to a value-type to allow further explosion.
+                        if ( dynamic_cast< const ast::ReferenceType *>( local->result.get() ) ) {
+                                local = new ast::CastExpr{ local, tupleType };
+                        }
+                        // Now we have to go across the tuple via indexing.
+                        for ( unsigned int i = 0 ; i < tupleType->size() ; ++i ) {
+                                ast::TupleIndexExpr * idx = new ast::TupleIndexExpr( local->location, local, i );
+                                explodeUnique( idx, arg, symtab, std::forward<Output>(out), isTupleAssign );
+                                // TODO: We need more input to figure out the exact lifetimes of these types.
+                                // delete idx;
+                        }
+                        // delete local;
+                }
+        } else {
+                // For atomic/non-tuple types, no explosion is used.
+                append( std::forward<Output>(out), expr, arg.env, arg.open, arg.need, arg.cost,
+                        arg.cvtCost );
+        }
+}
+
+/// expands a tuple-valued candidate into multiple candidates, each with a non-tuple type
+template< typename Output >
+void explode(
+        const ResolvExpr::Candidate & arg, const ast::SymbolTable & symtab, Output && out,
+        bool isTupleAssign = false
+) {
+        explodeUnique( arg.expr, arg, symtab, std::forward< Output >( out ), isTupleAssign );
+}
+
+/// explode list of candidates into flattened list of candidates
+template< typename Output >
+void explode(
+        const ResolvExpr::CandidateList & cands, const ast::SymbolTable & symtab, Output && out,
+        bool isTupleAssign = false
+) {
+        for ( const ResolvExpr::CandidateRef & cand : cands ) {
+                explode( *cand, symtab, std::forward< Output >( out ), isTupleAssign );
+        }
+}
+
 } // namespace Tuples
 

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, const
-                                ResolvExpr::AltList& rhs );
+                        Matcher( TupleAssignSpotter_old &spotter, const ResolvExpr::AltList& lhs,
+                                const ResolvExpr::AltList& rhs );
                         virtual ~Matcher() {}
+
                         virtual void match( std::list< Expression * > &out ) = 0;
                         ObjectDecl * newObject( UniqueName & namer, Expression * expr );
+
+                        void combineState( const ResolvExpr::Alternative& alt ) {
+                                compositeEnv.simpleCombine( alt.env );
+                                ResolvExpr::mergeOpenVars( openVars, alt.openVars );
+                                cloneAll( alt.need, need );
+                        }
+
+                        void combineState( const ResolvExpr::AltList& alts ) {
+                                for ( const ResolvExpr::Alternative& alt : alts ) { combineState( alt ); }
+                        }
+
                         ResolvExpr::AltList lhs, rhs;
-                        TupleAssignSpotter &spotter;
+                        TupleAssignSpotter_old &spotter;
                         ResolvExpr::Cost baseCost;
                         std::list< ObjectDecl * > tmpDecls;
                         ResolvExpr::TypeEnvironment compositeEnv;
+                        ResolvExpr::OpenVarSet openVars;
+                        ResolvExpr::AssertionSet need;
                 };
 
                 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 );
@@ -83 +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 );
@@ -122 +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()) ) {
@@ -210 +229 @@
         }
 
-        void TupleAssignSpotter::match() {
+        void TupleAssignSpotter_old::match() {
                 assert ( matcher != 0 );
 
@@ -245 +264 @@
                 }
 
-                // extract expressions from the assignment alternatives to produce a list of assignments that
-                // together form a single alternative
+                // extract expressions from the assignment alternatives to produce a list of assignments
+                // that together form a single alternative
                 std::list< Expression *> solved_assigns;
                 for ( ResolvExpr::Alternative & alt : current ) {
                         solved_assigns.push_back( alt.expr->clone() );
-                }
-                // combine assignment environments into combined expression environment
-                simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv );
+                        matcher->combineState( alt );
+                }
+
                 // xxx -- was push_front
-                currentFinder.get_alternatives().push_back( ResolvExpr::Alternative(
-                        new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv,
-                        ResolvExpr::sumCost( current ) + matcher->baseCost ) );
-        }
-
-        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter,
+                currentFinder.get_alternatives().push_back( ResolvExpr::Alternative{
+                        new TupleAssignExpr{ solved_assigns, matcher->tmpDecls }, matcher->compositeEnv,
+                        matcher->openVars,
+                        ResolvExpr::AssertionList( matcher->need.begin(), matcher->need.end() ),
+                        ResolvExpr::sumCost( current ) + matcher->baseCost } );
+        }
+
+        TupleAssignSpotter_old::Matcher::Matcher( TupleAssignSpotter_old &spotter,
                 const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs )
         : lhs(lhs), rhs(rhs), spotter(spotter),
           baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {
-                simpleCombineEnvironments( lhs.begin(), lhs.end(), compositeEnv );
-                simpleCombineEnvironments( rhs.begin(), rhs.end(), compositeEnv );
+                combineState( lhs );
+                combineState( rhs );
         }
 
@@ -297 +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() ) );
@@ -313 +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" );
@@ -331 +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" );
@@ -361 +382 @@
                 }
         }
+
+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 ~Matcher() = default;
+
+                        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( location, 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, 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, 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, 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
 

src/Tuples/TupleExpansion.cc

@@ -9 +9 @@
 // Author           : Rodolfo G. Esteves
 // Created On       : Mon May 18 07:44:20 2015
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Wed Jun 21 17:35:04 2017
-// Update Count     : 19
+// Last Modified By : Andrew Beach
+// Last Modified On : Fri Jul 19 14:39:00 2019
+// Update Count     : 22
 //
 
@@ -17 +17 @@
 #include <cassert>                // for assert
 #include <list>                   // for list
-
+#include <vector>
+
+#include "AST/CVQualifiers.hpp"
+#include "AST/Expr.hpp"
+#include "AST/Node.hpp"
+#include "AST/Type.hpp"
 #include "Common/PassVisitor.h"   // for PassVisitor, WithDeclsToAdd, WithGu...
 #include "Common/ScopedMap.h"     // for ScopedMap
@@ -58 +63 @@
                 };
 
-                struct TupleTypeReplacer : public WithDeclsToAdd, public WithGuards, public WithTypeSubstitution {
+                struct TupleTypeReplacer : public WithDeclsToAdd, public WithGuards, public WithConstTypeSubstitution {
                         Type * postmutate( TupleType * tupleType );
 
@@ -299 +304 @@
                 // produce the TupleType which aggregates the types of the exprs
                 std::list< Type * > types;
-                Type::Qualifiers qualifiers( Type::Const | Type::Volatile | Type::Restrict | Type::Lvalue | Type::Atomic | Type::Mutex );
+                Type::Qualifiers qualifiers( Type::Const | Type::Volatile | Type::Restrict | Type::Atomic | Type::Mutex );
                 for ( Expression * expr : exprs ) {
                         assert( expr->get_result() );
@@ -314 +319 @@
                 return new TupleType( qualifiers, types );
         }
+        const ast::Type * makeTupleType( const std::vector<ast::ptr<ast::Expr>> & exprs ) {
+                // produce the TupleType which aggregates the types of the exprs
+                std::vector<ast::ptr<ast::Type>> types;
+                ast::CV::Qualifiers quals{
+                        ast::CV::Const | ast::CV::Volatile | ast::CV::Restrict | ast::CV::Lvalue |
+                        ast::CV::Atomic | ast::CV::Mutex };
+
+                for ( const ast::Expr * expr : exprs ) {
+                        assert( expr->result );
+                        // if the type of any expr is void, the type of the entire tuple is void
+                        if ( expr->result->isVoid() ) return new ast::VoidType{};
+
+                        // qualifiers on the tuple type are the qualifiers that exist on all components
+                        quals &= expr->result->qualifiers;
+
+                        types.emplace_back( expr->result );
+                }
+
+                if ( exprs.empty() ) { quals = ast::CV::Qualifiers{}; }
+                return new ast::TupleType{ std::move(types), quals };
+        }
 
         TypeInstType * isTtype( Type * type ) {
@@ -324 +350 @@
         }
 
+        const TypeInstType * isTtype( const Type * type ) {
+                if ( const TypeInstType * inst = dynamic_cast< const TypeInstType * >( type ) ) {
+                        if ( inst->baseType && inst->baseType->kind == TypeDecl::Ttype ) {
+                                return inst;
+                        }
+                }
+                return nullptr;
+        }
+
+        const ast::TypeInstType * isTtype( const ast::Type * type ) {
+                if ( const ast::TypeInstType * inst = dynamic_cast< const ast::TypeInstType * >( type ) ) {
+                        if ( inst->base && inst->base->kind == ast::TypeVar::Ttype ) {
+                                return inst;
+                        }
+                }
+                return nullptr;
+        }
+
         namespace {
                 /// determines if impurity (read: side-effects) may exist in a piece of code. Currently gives a very crude approximation, wherein any function call expression means the code may be impure
@@ -329 +373 @@
                         ImpurityDetector( bool ignoreUnique ) : ignoreUnique( ignoreUnique ) {}
 
-                        void previsit( ApplicationExpr * appExpr ) {
+                        void previsit( const ApplicationExpr * appExpr ) {
                                 visit_children = false;
-                                if ( DeclarationWithType * function = InitTweak::getFunction( appExpr ) ) {
-                                        if ( function->get_linkage() == LinkageSpec::Intrinsic ) {
-                                                if ( function->get_name() == "*?" || function->get_name() == "?[?]" ) {
+                                if ( const DeclarationWithType * function = InitTweak::getFunction( appExpr ) ) {
+                                        if ( function->linkage == LinkageSpec::Intrinsic ) {
+                                                if ( function->name == "*?" || function->name == "?[?]" ) {
                                                         // intrinsic dereference, subscript are pure, but need to recursively look for impurity
                                                         visit_children = true;
@@ -342 +386 @@
                                 maybeImpure = true;
                         }
-                        void previsit( UntypedExpr * ) { maybeImpure = true; visit_children = false; }
-                        void previsit( UniqueExpr * ) {
+                        void previsit( const UntypedExpr * ) { maybeImpure = true; visit_children = false; }
+                        void previsit( const UniqueExpr * ) {
                                 if ( ignoreUnique ) {
                                         // bottom out at unique expression.
@@ -358 +402 @@
         } // namespace
 
-        bool maybeImpure( Expression * expr ) {
+        bool maybeImpure( const Expression * expr ) {
                 PassVisitor<ImpurityDetector> detector( false );
                 expr->accept( detector );
@@ -364 +408 @@
         }
 
-        bool maybeImpureIgnoreUnique( Expression * expr ) {
+        bool maybeImpureIgnoreUnique( const Expression * expr ) {
                 PassVisitor<ImpurityDetector> detector( true );
                 expr->accept( detector );

src/Tuples/Tuples.h

@@ -9 +9 @@
 // Author           : Rodolfo G. Esteves
 // Created On       : Mon May 18 07:44:20 2015
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 22 09:55:00 2017
-// Update Count     : 16
+// Last Modified By : Andrew Beach
+// Last Modified On : Tue Jun 18 09:36:00 2019
+// Update Count     : 18
 //
 
@@ -19 +19 @@
 #include <vector>
 
+#include "AST/Fwd.hpp"
+#include "AST/Node.hpp"
 #include "SynTree/Expression.h"
 #include "SynTree/Declaration.h"
@@ -24 +26 @@
 
 #include "ResolvExpr/AlternativeFinder.h"
+#include "ResolvExpr/CandidateFinder.hpp"
 
 namespace Tuples {
         // TupleAssignment.cc
-        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * assign, 
+        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * assign,
                 std::vector< ResolvExpr::AlternativeFinder >& args );
-        
+        void handleTupleAssignment( 
+                ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign, 
+                std::vector< ResolvExpr::CandidateFinder > & args );
+
         // TupleExpansion.cc
         /// expands z.[a, b.[x, y], c] into [z.a, z.b.x, z.b.y, z.c], inserting UniqueExprs as appropriate
@@ -42 +48 @@
         /// returns VoidType if any of the expressions have Voidtype, otherwise TupleType of the Expression result types
         Type * makeTupleType( const std::list< Expression * > & exprs );
+        const ast::Type * makeTupleType( const std::vector<ast::ptr<ast::Expr>> & exprs );
 
         /// returns a TypeInstType if `type` is a ttype, nullptr otherwise
         TypeInstType * isTtype( Type * type );
+        const TypeInstType * isTtype( const Type * type );
+        const ast::TypeInstType * isTtype( const ast::Type * type );
 
         /// returns true if the expression may contain side-effects.
-        bool maybeImpure( Expression * expr );
+        bool maybeImpure( const Expression * expr );
+        bool maybeImpure( const ast::Expr * expr );
 
-        /// returns true if the expression may contain side-effect, ignoring the presence of unique expressions.
-        bool maybeImpureIgnoreUnique( Expression * expr );
+        /// Returns true if the expression may contain side-effect,
+        /// ignoring the presence of unique expressions.
+        bool maybeImpureIgnoreUnique( const Expression * expr );
+        bool maybeImpureIgnoreUnique( const ast::Expr * expr );
 } // namespace Tuples
 

src/Tuples/module.mk

@@ -15 +15 @@
 ###############################################################################
 
-SRC +=  Tuples/TupleAssignment.cc \
-        Tuples/TupleExpansion.cc \
-        Tuples/Explode.cc
+SRC += Tuples/TupleAssignment.cc Tuples/TupleExpansion.cc Tuples/Explode.cc \
+        Tuples/Tuples.cc
+SRCDEMANGLE += Tuples/TupleAssignment.cc Tuples/TupleExpansion.cc Tuples/Explode.cc \
+        Tuples/Tuples.cc