//
// 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 : Fri Mar 17 09:43:03 2017
// Update Count     : 8
//

#include <algorithm>                       // for transform
#include <cassert>                         // for assert
#include <iterator>                        // for back_insert_iterator, back...
#include <list>                            // for _List_const_iterator, _Lis...
#include <memory>                          // for unique_ptr, allocator_trai...
#include <string>                          // for string
#include <vector>

#include "CodeGen/OperatorTable.h"
#include "Common/PassVisitor.h"
#include "Common/UniqueName.h"             // for UniqueName
#include "Common/utility.h"                // for zipWith
#include "Explode.h"                       // for explode
#include "InitTweak/GenInit.h"             // for genCtorInit
#include "InitTweak/InitTweak.h"           // for getPointerBase, isAssignment
#include "Parser/LinkageSpec.h"            // for Cforall
#include "ResolvExpr/Alternative.h"        // for AltList, Alternative
#include "ResolvExpr/AlternativeFinder.h"  // for AlternativeFinder, simpleC...
#include "ResolvExpr/Cost.h"               // for Cost
#include "ResolvExpr/Resolver.h"           // for resolveCtorInit
#include "ResolvExpr/TypeEnvironment.h"    // for TypeEnvironment
#include "ResolvExpr/typeops.h"            // for combos
#include "SynTree/Declaration.h"           // for ObjectDecl
#include "SynTree/Expression.h"            // for Expression, CastExpr, Name...
#include "SynTree/Initializer.h"           // for ConstructorInit, SingleInit
#include "SynTree/Statement.h"             // for ExprStmt
#include "SynTree/Type.h"                  // for Type, Type::Qualifiers
#include "SynTree/TypeSubstitution.h"      // for TypeSubstitution
#include "SynTree/Visitor.h"               // for Visitor

#if 0
#define PRINT(x) x
#else
#define PRINT(x)
#endif

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

	  private:
		void match();

		struct Matcher {
		  public:
			Matcher( TupleAssignSpotter &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;
			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,
				const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
			virtual void match( std::list< Expression * > &out );
		};

		struct MultipleAssignMatcher : public Matcher {
		  public:
			MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
				const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
			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
	bool isTuple( Expression *expr ) {
		if ( ! expr ) return false;
		assert( expr->result );
		return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() );
	}

	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 refToTuple( Expression *expr ) {
		assert( expr->get_result() );
		// also check for function returning tuple of reference types
		if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
			return refToTuple( castExpr->get_arg() );
		} else {
			return isTuple( expr );
		}
		return false;
	}

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

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

	void TupleAssignSpotter::spot( UntypedExpr * expr,
			std::vector<ResolvExpr::AlternativeFinder> &args ) {
		if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
			if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
				fname = op->get_name();

				// AlternativeFinder will naturally handle this case case, if it's legal
				if ( args.size() == 0 ) return;

				// if an assignment only takes 1 argument, that's odd, but maybe someone wrote
				// the function, in which case AlternativeFinder will handle it normally
				if ( args.size() == 1 && CodeGen::isAssignment( fname ) ) return;

				// look over all possible left-hand-sides
				for ( ResolvExpr::Alternative& lhsAlt : args[0] ) {
					// skip non-tuple LHS
					if ( ! refToTuple(lhsAlt.expr) ) continue;

					// explode is aware of casts - ensure every LHS expression is sent into explode
					// with a reference cast
					// xxx - this seems to change the alternatives before the normal
					//  AlternativeFinder flow; maybe this is desired?
					if ( ! dynamic_cast<CastExpr*>( lhsAlt.expr ) ) {
						lhsAlt.expr = new CastExpr( lhsAlt.expr,
								new ReferenceType( Type::Qualifiers(),
									lhsAlt.expr->result->clone() ) );
					}

					// explode the LHS so that each field of a tuple-valued-expr is assigned
					ResolvExpr::AltList lhs;
					explode( lhsAlt, currentFinder.get_indexer(), back_inserter(lhs), true );
					for ( ResolvExpr::Alternative& alt : lhs ) {
						// each LHS value must be a reference - some come in with a cast expression,
						// if not just cast to reference here
						if ( ! dynamic_cast<ReferenceType*>( alt.expr->get_result() ) ) {
							alt.expr = new CastExpr( alt.expr,
								new ReferenceType( Type::Qualifiers(),
									alt.expr->get_result()->clone() ) );
						}
					}

					if ( args.size() == 1 ) {
						// mass default-initialization/destruction
						ResolvExpr::AltList rhs{};
						matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
						match();
					} else if ( args.size() > 2 ) {
						// expand all possible RHS possibilities
						// TODO build iterative version of this instead of using combos
						std::vector< ResolvExpr::AltList > rhsAlts;
						combos( std::next(args.begin(), 1), args.end(),
							std::back_inserter( rhsAlts ) );
						for ( const ResolvExpr::AltList& rhsAlt : rhsAlts ) {
							// multiple assignment
							ResolvExpr::AltList rhs;
							explode( rhsAlt, currentFinder.get_indexer(),
								std::back_inserter(rhs), true );
							matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
							match();
						}
					} else {
						for ( const ResolvExpr::Alternative& rhsAlt : args[1] ) {
							ResolvExpr::AltList rhs;
							if ( isTuple(rhsAlt.expr) ) {
								// multiple assignment
								explode( rhsAlt, currentFinder.get_indexer(),
									std::back_inserter(rhs), true );
								matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
							} else {
								// mass assignment
								rhs.push_back( rhsAlt );
								matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
							}
							match();
						}
					}
				}
			}
		}
	}

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

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

		if ( ! matcher->lhs.empty() || ! matcher->rhs.empty() ) {
			// if both lhs and rhs are empty then this is the empty tuple case, wherein it's okay for new_assigns to be empty.
			// if not the empty tuple case, return early so that no new alternatives are generated.
			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 ) {
			PRINT(
				std::cerr << "== resolving tuple assign ==" << std::endl;
				std::cerr << *i << std::endl;
			)

			ResolvExpr::AlternativeFinder finder{ currentFinder.get_indexer(),
				matcher->compositeEnv };

			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() );
			matcher->combineState( alt );
		}
		
		// xxx -- was push_front
		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::Matcher::Matcher( TupleAssignSpotter &spotter,
		const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs )
	: lhs(lhs), rhs(rhs), spotter(spotter),
	  baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {
		combineState( lhs ); 
		combineState( rhs );
	}

	UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
		assert( left );
		std::list< Expression * > args;
		args.push_back( new VariableExpr( left ) );
		// args.push_back( new AddressExpr( new VariableExpr( left ) ) );
		if ( right ) args.push_back( new VariableExpr( right ) );
		if ( left->type->referenceDepth() > 1 && CodeGen::isConstructor( fname ) ) {
			args.front() = new AddressExpr( args.front() );
			if ( right ) args.back() = new AddressExpr( args.back() );
			return new UntypedExpr( new NameExpr( "?=?" ), args );
		} else {
			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, and adds the bindings to the compositeEnv
	// xxx - maybe this should happen in alternative finder for every StmtExpr?
	struct EnvRemover {
		void previsit( ExprStmt * stmt ) {
			assert( compositeEnv );
			if ( stmt->expr->env ) {
				compositeEnv->add( *stmt->expr->env );
				delete stmt->expr->env;
				stmt->expr->env = nullptr;
			}
		}

		ResolvExpr::TypeEnvironment * compositeEnv = nullptr;
	};

	ObjectDecl * TupleAssignSpotter::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() ) );
		// if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
		if ( ! dynamic_cast< ReferenceType * >( expr->result ) ) {
			ConstructorInit * ctorInit = InitTweak::genCtorInit( ret );
			ret->init = ctorInit;
			ResolvExpr::resolveCtorInit( ctorInit, spotter.currentFinder.get_indexer() ); // resolve ctor/dtors for the new object
			PassVisitor<EnvRemover> rm; // remove environments from subexpressions of StmtExprs
			rm.pass.compositeEnv = &compositeEnv;
			ctorInit->accept( rm );
		}
		PRINT( std::cerr << "new object: " << ret << std::endl; )
		return ret;
	}

	void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
		static UniqueName lhsNamer( "__massassign_L" );
		static UniqueName rhsNamer( "__massassign_R" );
		// empty tuple case falls into this matcher, hence the second part of the assert
		assert( (! lhs.empty() && rhs.size() <= 1) || (lhs.empty() && rhs.empty()) );

		// xxx - may need to split this up into multiple declarations, because potential conversion to references
		//  probably should not reference local variable - see MultipleAssignMatcher::match
		ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
		for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
			// create a temporary object for each value in the lhs and create a call involving the rhs
			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" );

		if ( lhs.size() == rhs.size() ) {
			// produce a new temporary object for each value in the lhs and rhs and pairwise create the calls
			std::list< ObjectDecl * > ltmp;
			std::list< ObjectDecl * > rtmp;
			for ( auto p : group_iterate( lhs, rhs ) ) {
				ResolvExpr::Alternative & lhsAlt = std::get<0>(p);
				ResolvExpr::Alternative & rhsAlt = std::get<1>(p);
				// convert RHS to LHS type minus one reference -- important for the case where LHS is && and RHS is lvalue, etc.
				ReferenceType * lhsType = strict_dynamic_cast<ReferenceType *>( lhsAlt.expr->result );
				rhsAlt.expr = new CastExpr( rhsAlt.expr, lhsType->base->clone() );
				ObjectDecl * lobj = newObject( lhsNamer, lhsAlt.expr );
				ObjectDecl * robj = newObject( rhsNamer, rhsAlt.expr );
				out.push_back( createFunc(spotter.fname, lobj, robj) );
				ltmp.push_back( lobj );
				rtmp.push_back( robj );

				// resolve the cast expression so that rhsAlt return type is bound by the cast type as needed, and transfer the resulting environment
				ResolvExpr::AlternativeFinder finder{ spotter.currentFinder.get_indexer(), compositeEnv };
				finder.findWithAdjustment( rhsAlt.expr );
				assert( finder.get_alternatives().size() == 1 );
				compositeEnv = std::move( finder.get_alternatives().front().env );
			}
			tmpDecls.splice( tmpDecls.end(), ltmp );
			tmpDecls.splice( tmpDecls.end(), rtmp );
		}
	}

	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 Tuples

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