source: src/Tuples/TupleAssignment.cc @ 5af62f1

//
// 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 : Peter A. Buhr
// Last Modified On : Mon May 18 15:02:53 2015
// Update Count     : 2
//

#include "ResolvExpr/AlternativeFinder.h"
#include "ResolvExpr/Alternative.h"
#include "ResolvExpr/typeops.h"
#include "SynTree/Expression.h"
#include "TupleAssignment.h"
#include "Common/SemanticError.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, std::list<ResolvExpr::AltList> &possibilities );

          private:
                void match();
                // records for assignment generation
                struct Options {
                        std::list< ResolvExpr::AltList > get_best();
                        void print( std::ostream & );
                        int size() const { return options.size(); }
                        bool empty() const { return options.empty(); }
                        typedef std::list< ResolvExpr::AltList >::iterator iterator;
                        iterator begin() { return options.begin(); }
                        iterator end() { return options.end(); }

                        std::list< ResolvExpr::AltList > options;
                };

                class Matcher {
                  public:
                        Matcher( TupleAssignSpotter &spotter, Expression *_lhs, Expression *_rhs );
                        virtual ~Matcher() {}
                        virtual void match( std::list< Expression * > &out ) = 0;
                        virtual void solve( std::list< Expression * > &assigns ) = 0;
                        static UntypedExpr *createAssgn( Expression *left, Expression *right );
                  protected:
                        std::list< Expression * > lhs, rhs;
                        TupleAssignSpotter &spotter;
                };

                class MassAssignMatcher : public Matcher {
                  public:
                        MassAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) {
                                this->rhs.push_back( rhs );
                        }
                        virtual void match( std::list< Expression * > &out );
                        virtual void solve( std::list< Expression * > &assigns );
                };

                class MultipleAssignMatcher : public Matcher {
                  public:
                        MultipleAssignMatcher( TupleAssignSpotter &spot, Expression *lhs, Expression *rhs );
                        virtual void match( std::list< Expression * > &out );
                        virtual void solve( std::list< Expression * > &assigns );
                };

                ResolvExpr::AlternativeFinder &currentFinder;
                Expression *rhs, *lhs;
                Matcher *matcher = nullptr;
                Options options;
        };

        bool isTupleVar( DeclarationWithType *decl ) {
                return dynamic_cast< TupleType * >( decl->get_type() );
        }

        /// 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;

                // xxx - used to include cast to varExpr and call to isTupleVar, but this doesn't seem like it should be necessary
                return dynamic_cast<TupleExpr *>(expr) || expr->get_results().size() > 1;
        }

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

        bool isTupleExpr( Expression *expr ) {
                return expr->get_results().size() > 1;
        }

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

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

        void TupleAssignSpotter::spot( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
                if (  NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) {
                        if ( assgnop->get_name() == std::string("?=?") ) {
                                for ( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
                                        assert( ali->size() == 2 );
                                        ResolvExpr::Alternative op1 = ali->front(), op2 = ali->back();

                                        MultipleAssignMatcher multiMatcher( *this, op1.expr, op2.expr );
                                        MassAssignMatcher massMatcher( *this, op1.expr, op2.expr );
                                        if ( pointsToTuple(op1.expr) ) { // also handles tuple vars
                                                if ( isTuple( op2.expr ) ) {
                                                        matcher = &multiMatcher;
                                                } else {
                                                        // mass assignment
                                                        matcher = &massMatcher;
                                                }
                                                match();
                                        } else if ( isTuple( op2.expr ) ) {
                                                throw SemanticError("Cannot assign a tuple value into a non-tuple lvalue.", expr);
                                        }
                                }
                        }
                }
        }

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

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

                if ( new_assigns.empty() ) return;
                std::list< Expression * > solved_assigns;
                ResolvExpr::AltList solved_alts;
                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() );
                        finder.findWithAdjustment(*i);
                        // 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( finder.get_alternatives().front() );
                        solved_assigns.push_back( alts.front().expr->clone() );
                }
                options.options.push_back( current );

                matcher->solve( new_assigns );
        }

        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : spotter(spotter) {
                // xxx - shouldn't need to be &<tuple-expr>, just &<lvalue-tuple-type>
                if (AddressExpr *addr = dynamic_cast<AddressExpr *>(lhs) )
                        if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) )
                                std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->lhs) );
        }

        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) {

                if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(rhs) )
                        std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->rhs) );
        }

        UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) {
                assert( left && right );
                std::list< Expression * > args;
                args.push_back( new AddressExpr( left->clone() ) );
                args.push_back( right->clone() );
                return new UntypedExpr( new NameExpr( "?=?" ), args );
        }

        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
                assert ( ! lhs.empty() && rhs.size() == 1);

                for ( Expression * l : lhs ) {
                        out.push_back( createAssgn( l, rhs.front() ) );
                }
        }

        void TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) {
                assert( ! spotter.options.empty() );
                ResolvExpr::AltList winners;
                for ( std::list< ResolvExpr::AltList >::iterator i = spotter.options.begin(); i != spotter.options.end(); ++i ) {
                        findMinCost( i->begin(), i->end(), back_inserter(winners) );
                }

                std::list< Expression *> solved_assigns;
                for ( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i ) {
                        solved_assigns.push_back( i->expr );
                }
                spotter.currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns), spotter.currentFinder.get_environ(), ResolvExpr::Cost() ) );
        }

        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
                // xxx - need more complicated matching?
                if ( lhs.size() == rhs.size() ) {
                        zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn );
                }
        }

        void TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) {
                // options.print( std::cerr );
                std::list< ResolvExpr::AltList > best = spotter.options.get_best();
                if ( best.size() == 1 ) {
                        std::list<Expression *> solved_assigns;
                        for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ) {
                                solved_assigns.push_back( i->expr );
                        }
                        /* assigning cost zero? */
                        spotter.currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns), spotter.currentFinder.get_environ(), ResolvExpr::Cost() ) );
                }
        }

        std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() {
                std::list< ResolvExpr::AltList > ret;
                std::list< ResolvExpr::AltList > solns;
                for ( ResolvExpr::AltList & i : options ) {
                        ResolvExpr::AltList current;
                        findMinCost( i.begin(), i.end(), back_inserter(current) );
                        solns.push_back( ResolvExpr::AltList(current.begin(), current.end()) );
                }
                // need to combine -- previously "lift_intersection", which
                // did some madness involving, effectively, the intersection of
                // a bunch of AltLists
                std::list<ResolvExpr::AltList> result = solns;
                if ( result.size() != 1 ) {
                        throw SemanticError("Ambiguous tuple expression");
                }
                ret.push_back( *result.begin() );
                return ret;
        }

        void TupleAssignSpotter::Options::print( std::ostream &ostr ) {
                for ( ResolvExpr::AltList & l : options ) {
                        for ( ResolvExpr::Alternative & alt : l ) {
                                alt.print( ostr );
                                ostr << " ";
                        }
                        ostr << std::endl;
                } // for
        }
} // namespace Tuples

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