source: src/Tuples/TupleAssignment.cc @ 4c8621ac

//
// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// TupleAssignment.cc --
//
// Author           : Rodolfo G. Esteves
// Created On       : Mon May 18 07:44:20 2015
// Last Modified By : Rob Schluntz
// Last Modified On : Wed Nov 9 13:48:42 2016
// Update Count     : 2
//

#include "ResolvExpr/AlternativeFinder.h"
#include "ResolvExpr/Alternative.h"
#include "ResolvExpr/typeops.h"
#include "SynTree/Expression.h"
#include "SynTree/Initializer.h"
#include "Tuples.h"
#include "Explode.h"
#include "Common/SemanticError.h"
#include "InitTweak/InitTweak.h"
#include "InitTweak/GenInit.h"

#include <functional>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cassert>
#include <set>
#include <unordered_set>

namespace Tuples {
        class TupleAssignSpotter {
          public:
                // dispatcher for Tuple (multiple and mass) assignment operations
                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
                void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities );

          private:
                void match();
                void handleEmptyTuple( const ResolvExpr::AltList & alts );

                struct Matcher {
                  public:
                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
                        virtual ~Matcher() {}
                        virtual void match( std::list< Expression * > &out ) = 0;
                        ObjectDecl * newObject( UniqueName & namer, Expression * expr );
                        ResolvExpr::AltList lhs, rhs;
                        TupleAssignSpotter &spotter;
                        ResolvExpr::Cost baseCost;
                        std::list< ObjectDecl * > tmpDecls;
                        ResolvExpr::TypeEnvironment compositeEnv;
                };

                struct MassAssignMatcher : public Matcher {
                  public:
                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
                        virtual void match( std::list< Expression * > &out );
                };

                struct MultipleAssignMatcher : public Matcher {
                  public:
                        MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts );
                        virtual void match( std::list< Expression * > &out );
                };

                ResolvExpr::AlternativeFinder &currentFinder;
                std::string fname;
                std::unique_ptr< Matcher > matcher;
        };

        /// true if expr is an expression of tuple type, i.e. a tuple expression, tuple variable, or MRV (multiple-return-value) function
        bool isTuple( Expression *expr ) {
                if ( ! expr ) return false;
                assert( expr->has_result() );
                return dynamic_cast<TupleExpr *>(expr) || expr->get_result()->size() > 1;
        }

        template< typename AltIter >
        bool isMultAssign( AltIter begin, AltIter end ) {
                // multiple assignment if more than one alternative in the range or if
                // the alternative is a tuple
                if ( begin == end ) return false;
                if ( isTuple( begin->expr ) ) return true;
                return ++begin != end;
        }

        bool pointsToTuple( Expression *expr ) {
                // also check for function returning tuple of reference types
                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
                        return pointsToTuple( castExpr->get_arg() );
                } else if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) {
                        return isTuple( addr->get_arg() );
                }
                return false;
        }

        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
                TupleAssignSpotter spotter( currentFinder );
                spotter.spot( expr, possibilities );
        }

        TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
                : currentFinder(f) {}

        void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
                        if ( InitTweak::isCtorDtorAssign( op->get_name() ) ) {
                                fname = op->get_name();
                                for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
                                        if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
                                        if ( ali->size() <= 1 && InitTweak::isAssignment( op->get_name() ) ) {
                                                // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
                                                continue;
                                        }

                                        assert( ! ali->empty() );
                                        // grab args 2-N and group into a TupleExpr
                                        const ResolvExpr::Alternative & alt1 = ali->front();
                                        auto begin = std::next(ali->begin(), 1), end = ali->end();
                                        if ( pointsToTuple(alt1.expr) ) {
                                                if ( isMultAssign( begin, end ) ) {
                                                        matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
                                                } else {
                                                        // mass assignment
                                                        matcher.reset( new MassAssignMatcher( *this,  *ali ) );
                                                }
                                                match();
                                        } else {
                                                // handle empty case specially. It is easy to cause conflicts for tuple assignment when we consider any expression with Tuple type to be a tuple.
                                                // Instead, only tuple expressions and expressions with at least 2 results are considered tuples for tuple assignment. This most obviously leaves out the
                                                // nullary and unary cases. The unary case is handled nicely by the alternative finder as is. For example, an expression of type [int] will be exploded
                                                // into a list of one element (combined with the RHS elements), which will easily allow for intrinsic construction. This seems like a best case scenario anyway,
                                                // since intrinsic construction is much simpler from a code-gen perspective than tuple construction is.
                                                // This leaves the empty case, which is not easily handled by existing alternative finder logic. Instead, it seems simple enough to hanlde here that if the left
                                                // side is an empty tuple, then the right side is allowed to be either an empty tuple or an empty list. Fortunately, these cases are identical when exploded.
                                                handleEmptyTuple( *ali );
                                        }
                                }
                        }
                }
        }

        void TupleAssignSpotter::match() {
                assert ( matcher != 0 );

                std::list< Expression * > new_assigns;
                matcher->match( new_assigns );

                if ( new_assigns.empty() ) return;
                ResolvExpr::AltList current;
                // now resolve new assignments
                for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
                        ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
                        try {
                                finder.findWithAdjustment(*i);
                        } catch (...) {
                                return; // no match should not mean failure, it just means this particular tuple assignment isn't valid
                        }
                        // prune expressions that don't coincide with
                        ResolvExpr::AltList alts = finder.get_alternatives();
                        assert( alts.size() == 1 );
                        assert( alts.front().expr != 0 );
                        current.push_back( alts.front() );
                }

                // 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 );
                currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current  ) + matcher->baseCost ) );
        }

        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
                assert( ! alts.empty() );
                // combine argument environments into combined expression environment
                simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );

                ResolvExpr::Alternative lhsAlt = alts.front();
                // peel off the cast that exists on ctor/dtor expressions
                bool isCast = false;
                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
                        lhsAlt.expr = castExpr->get_arg();
                        castExpr->set_arg( nullptr );
                        delete castExpr;
                        isCast = true;
                }

                // explode the lhs so that each field of the tuple-valued-expr is assigned.
                explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs) );

                // and finally, re-add the cast to each lhs expr, so that qualified tuple fields can be constructed
                if ( isCast ) {
                        for ( ResolvExpr::Alternative & alt : lhs ) {
                                Expression *& expr = alt.expr;
                                Type * castType = expr->get_result()->clone();
                                Type * type = InitTweak::getPointerBase( castType );
                                assert( type );
                                type->get_qualifiers() -= Type::Qualifiers(true, true, true, false, true, true);
                                type->set_isLvalue( true ); // xxx - might not need this
                                expr = new CastExpr( expr, castType );
                        }
                }
        }

        TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
                assert( alts.size() == 1 || alts.size() == 2 );
                if ( alts.size() == 2 ) {
                        rhs.push_back( alts.back() );
                }
        }

        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
                // explode the rhs so that each field of the tuple-valued-expr is assigned.
                explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs) );
        }

        UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
                assert( left );
                std::list< Expression * > args;
                args.push_back( new AddressExpr( UntypedExpr::createDeref( new VariableExpr( left ) ) ) );
                // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
                if ( right ) args.push_back( new VariableExpr( right ) );
                return new UntypedExpr( new NameExpr( fname ), args );
        }

        // removes environments from subexpressions within statement exprs, which could throw off later passes like those in Box which rely on PolyMutator.
        // xxx - maybe this should happen in alternative finder for every StmtExpr?
        // xxx - it's possible that these environments could contain some useful information. Maybe the right thing to do is aggregate the environments and pass the aggregate back to be added into the compositeEnv
        struct EnvRemover : public Visitor {
                virtual void visit( ExprStmt * stmt ) {
                        delete stmt->get_expr()->get_env();
                        stmt->get_expr()->set_env( nullptr );
                        Visitor::visit( stmt );
                }
        };

        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
                assert( expr->has_result() && ! expr->get_result()->isVoid() );
                ObjectDecl * ret = new ObjectDecl( namer.newName(), DeclarationNode::NoStorageClass, LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
                ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
                ret->set_init( ctorInit );
                ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
                EnvRemover rm; // remove environments from subexpressions of StmtExprs
                ctorInit->accept( rm );
                return ret;
        }

        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
                static UniqueName lhsNamer( "__massassign_L" );
                static UniqueName rhsNamer( "__massassign_R" );
                assert( ! lhs.empty() && rhs.size() <= 1 );

                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
                for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
                        tmpDecls.push_back( ltmp );
                }
                if ( rtmp ) tmpDecls.push_back( rtmp );
        }

        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
                static UniqueName lhsNamer( "__multassign_L" );
                static UniqueName rhsNamer( "__multassign_R" );

                // xxx - need more complicated matching?
                if ( lhs.size() == rhs.size() ) {
                        std::list< ObjectDecl * > ltmp;
                        std::list< ObjectDecl * > rtmp;
                        std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), [&]( ResolvExpr::Alternative & alt ){
                                return newObject( lhsNamer, alt.expr );
                        });
                        std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), [&]( ResolvExpr::Alternative & alt ){
                                return newObject( rhsNamer, alt.expr );
                        });
                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
                        tmpDecls.splice( tmpDecls.end(), ltmp );
                        tmpDecls.splice( tmpDecls.end(), rtmp );
                }
        }

        // empty case is okay when right side is also "empty" (empty explosion handles no argument case as well as empty tuple case)
        void TupleAssignSpotter::handleEmptyTuple( const ResolvExpr::AltList & alts ) {
                assert( ! alts.empty() );
                Expression * lhs = alts.front().expr;
                if ( PointerType * ptrType = dynamic_cast< PointerType * >( lhs->get_result() ) ) {
                        if ( TupleType * tupleType = dynamic_cast< TupleType * >( ptrType->get_base() ) ) {
                                if ( tupleType->size() == 0 ) {
                                        ResolvExpr::AltList rhs;
                                        explode( std::next(alts.begin(), 1), alts.end(), currentFinder.get_indexer(), back_inserter(rhs) );
                                        if ( rhs.empty() ) {
                                                // okay, no other case is allowed
                                                ResolvExpr::TypeEnvironment compositeEnv;
                                                simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
                                                currentFinder.get_alternatives().push_front( ResolvExpr::Alternative( new TupleAssignExpr( std::list< Expression * >(), std::list< ObjectDecl * >() ), compositeEnv, ResolvExpr::sumCost( alts ) ) );
                                        }
                                }
                        }
                }
        }
} // namespace Tuples

// Local Variables: //
// tab-width: 4 //
// mode: c++ //
// compile-command: "make install" //
// End: //